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

• 成果类型: Article
• 署名作者: Cecchetto, Federica; Traub, Vera; Zenklusen, Rico
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Bonn; University of Bonn
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02018-3
• 发表日期: 2024
• 页码: 515-549
• 关键词: approximation algorithms

摘要

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.