论文标题
比$ \ frac {4} {3} $更好 - 叶子 - 叶到叶树的近似值和连接性增强
Better-Than-$\frac{4}{3}$-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
论文作者
论文摘要
连接增强问题（CAP）以及称为树增强问题（TAP）的众所周知的特殊情况是最基本的网络设计问题之一。最近，人们引起了人们的兴趣，以找到近似算法的尾水和帽子的保证量低于$ 2 $，最终以相当复杂的技术为$ 1.393 $的当前最佳近似因素。 我们为众所周知的叶叶实例特殊情况提供了一种新的且基于简单的基于匹配的方法。将我们的工作与先前的技术相结合，我们很容易获得$（\ frac {4} {3}+ε）$ - 叶到叶盖的近似值，通过返回我们的解决方案和现有方法之一。在我们工作之前，$ \ frac {4} {3} $ - 保证仅在树上的叶子到叶子tap实例$ 2 $的情况下才闻名。此外，当将我们的技术与最近引入的堆栈分析方法相结合时，这是上述$ 1.393 $ - APPROXIMATION的一部分，我们可以将近似因子进一步提高到$ 1.29 $，首先获得低于$ \ frac {4} {4} {3} $的因子，用于非trigial tap/cap/cap/cap/cap/cap/cap/cap/cap的Intercantes。
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 $(\frac{4}{3}+ε)$-approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a $\frac{4}{3}$-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}$ for a nontrivial class of TAP/CAP instances.
