Better-than-4/3-approximations for leaf-to-leaf tree and connectivity augmentation

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 + epsilon)-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.

Automated summary

The Connectivity Augmentation Problem (CAP) and the Tree Augmentation Problem (TAP) are fundamental Network Design problems. There has been an increase in interest in finding approximation algorithms for both TAP and CAP with guarantees below 2. This paper presents a new matching-based method for the leaf-to-leaf instances of CAP, achieving better approximation results by combining previous techniques. By combining with a stack analysis approach, an improved approximation factor for a nontrivial class of TAP/CAP instances is obtained for the first time.