Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
share
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+ϵ)-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-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 4/3 for a nontrivial class of TAP/CAP instances.
READ FULL TEXT