Better-than-$$\frac{4}{3}$$-approximations for leaf-to-leaf tree and connectivity augmentation
针对叶到叶实例的连通性增强问题，提出一种基于匹配的简单方法，结合现有技术得到4/3+ε近似比，进一步结合栈分析将因子降至1.29，首次突破4/3。
Abstract The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a $$(4/3+\varepsilon )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>4</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a $$4/3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below $$\frac{4}{3}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> </mml:math> for a nontrivial class of TAP/CAP instances.