Approximation Algorithms for Steiner Connectivity Augmentation

References

• [1] Basavaraju M, Fomin FV, Golovach PA, Misra P, Ramanujan MS, Saurabh S (2014) Parameterized algorithms to preserve connectivity. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Automata Languages Programming – 41st Internat. Colloquium, ICALP 2014, Proc., Part I, Lecture Notes in Computer Science, vol. 8572 (Springer, Berlin, Heidelberg), 800–811.Google Scholar
• [2] Borchers A, Du DZ (1997) Thek-Steiner ratio in graphs. SIAM J. Comput. 26(3):857–869.Crossref, Google Scholar
• [3] Bosch-Calvo M, Garg M, Grandoni F, Hommelsheim F, Ameli AJ, Lindermayr A (2025) A 5/4-approximation for two-edge connectivity. Koucký M, Bansal N, eds. Proc. 57th Annual ACM Sympos. Theory Comput. (ACM, New York), 653–664.Google Scholar
• [4] Cecchetto F, Traub V, Zenklusen R (2023) Bridging the gap between tree and connectivity augmentation: Unified and stronger approaches. SIAM J. Comput. STOC21–26–STOC21–103.Crossref, Google Scholar
• [5] Cheriyan J, Gao Z (2018) Approximating (unweighted) tree augmentation via lift-and-project, part I: Stemless TAP. Algorithmica 80(2):530–559.Crossref, Google Scholar
• [6] Cheriyan J, Gao Z (2018) Approximating (unweighted) tree augmentation via lift-and-project, part II. Algorithmica 80(2):608–651.Crossref, Google Scholar
• [7] Cheriyan J, Karloff H, Khandekar R, Könemann J (2008) On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4):399–401.Crossref, Google Scholar
• [8] Cohen N, Nutov Z (2013) A (1+ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius. Theoret. Comput. Sci. 489–490:67–74.Crossref, Google Scholar
• [9] Cohen-Addad V, Drygala M, Klein N, Svensson O (2026) A strong linear programming relaxation for weighted tree augmentation. CoRR. abs/2603.29582:1–75.Google Scholar
• [10] Dinitz Y, Vainshtein A (1994) The connectivity carcass of a vertex subset in a graph and its incremental maintenance. Proc. Twenty-Sixth Annual ACM Sympos. Theory Comput. (ACM, New York), 716–725.Google Scholar
• [11] Dinitz EA, Karzanov AV, Lomonosov MV (1976) On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, 290–306.Google Scholar
• [12] Dreyfus SE, Wagner RA (1971) The Steiner problem in graphs. Networks 1(3):195–207.Crossref, Google Scholar
• [13] Fiorini S, Groß M, Könemann J, Sanità L (2018) Approximating weighted tree augmentation via Chvátal-Gomory cuts. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 817–831.Google Scholar
• [14] Frederickson GN, Ja’Ja’ J (1981) Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2):270–283.Crossref, Google Scholar
• [15] Gálvez W, Grandoni F, Jabal Ameli A, Sornat K (2021) On the cycle augmentation problem: Hardness and approximation algorithms. Theory Comput. Systems 65(6):985–1008.Crossref, Google Scholar
• [16] Garg M, Grandoni F, Ameli AJ (2023) Improved approximation for two-edge-connectivity. Bansal N, Nagarajan V, eds. Proc. 2023 ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2368–2410.Google Scholar
• [17] Grandoni F, Ameli AJ, Traub V (2022) Breaching the 2-approximation barrier for the forest augmentation problem. Leonardi S, Gupta A, eds. STOC ‘22: 54th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1598–1611.Google Scholar
• [18] Hunkenschröder C, Vempala SS, Vetta A (2019) A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem. ACM Trans. Algorithms 15(4):55:1–55:28.Crossref, Google Scholar
• [19] Jain K (2001) A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1):39–60.Crossref, Google Scholar
• [20] Kortsarz G, Krauthgamer R, Lee JR (2004) Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput. 33(3):704–720.Crossref, Google Scholar
• [21] Nutov Z (2010) Approximating Steiner networks with node-weights. SIAM J. Comput. 39(7):3001–3022.Crossref, Google Scholar
• [22] Parekh O, Ravi R, Zlatin M (2022) On small-depth tree augmentations. Oper. Res. Lett. 50(6):667–673.Crossref, Google Scholar
• [23] Ravi R, Zhang W, Zlatin M (2023) Approximation algorithms for Steiner tree augmentation problems. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2429–2448.Google Scholar
• [24] Sebö A, Vygen J (2014) Shorter tours by nicer ears: 7/5-approximation for the graph-tsp, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Comb 34(5):597–629.Google Scholar
• [25] Traub V, Zenklusen R (2021) A better-than-2 approximation for weighted tree augmentation. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1–12.Google Scholar
• [26] Traub V, Zenklusen R (2022) Local search for weighted tree augmentation and Steiner tree. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 3253–3272.Google Scholar
• [27] Traub V, Zenklusen R (2023) A (1.5+ε)-approximation algorithm for weighted connectivity augmentation. Saha B, Servedio RA, eds. Proc. 55th Annual ACM Sympo. Theory Comput. (ACM, New York), 1820–1833.Google Scholar
• [28] Traub V, Zenklusen R (2025) Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree. J. ACM 72(2):16:1–16:40.Google Scholar
• [29] Williamson DP, Goemans MX, Mihail M, Vazirani VV (1993) A primal-dual approximation algorithm for generalized Steiner network problems. Proc. Twenty-Fifth Annual ACM Sympos. Theory Comput. (ACM, New York), 708–717.Google Scholar