Better-Than--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 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 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 -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height . Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned -approximation, we can further improve the approximation factor to , obtaining for the first time a factor below for a nontrivial class of TAP/CAP instances.