{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T02:22:29Z","timestamp":1789784549741,"version":"4.0.1"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2015\/18\/E\/ST6\/00456"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SNF Excellence","award":["200020B_182865\/1"],"award-info":[{"award-number":["200020B_182865\/1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges\/nodes. The connectivity augmentation problem ([Formula: see text]) is arguably one of the most basic problems in this area: given a [Formula: see text](-edge)-connected graph [Formula: see text] and a set of extra edges ( links), select a minimum cardinality subset [Formula: see text] of links such that adding [Formula: see text] to [Formula: see text] increases its edge connectivity to [Formula: see text]. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\u00e1j\u00e1, SIAM J. Comput., 10 (1981), pp. 270\u2013283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290\u2013306] that [Formula: see text] can be reduced to the case [Formula: see text], also known as the t ree augmentation problem ([Formula: see text]) for odd [Formula: see text], and to the case [Formula: see text], also known as the c actus augmentation problem ([Formula: see text]) for even [Formula: see text]. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC\u201920, ACM, New York, 2020, pp. 815\u2013825], several better than 2 approximation algorithms were known for [Formula: see text], culminating with a recent [Formula: see text] approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC\u201918, ACM, New York, 1918, pp. 632\u2013645]. However, for [Formula: see text] the best known approximation was 2. In this paper we breach the 2 approximation barrier for [Formula: see text], hence, for [Formula: see text], by presenting a polynomial-time [Formula: see text] approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for [Formula: see text] either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP\u2009\u201914, Springer, Berlin, 2014, pp. 800\u2013811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we \u201copen the box\u201d and exploit the specific properties of the instances of a Steiner tree arising from [Formula: see text]. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.<\/jats:p>","DOI":"10.1137\/21m1421143","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T14:04:24Z","timestamp":1684850664000},"page":"718-739","source":"Crossref","is-referenced-by-count":10,"title":["Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree"],"prefix":"10.1137","volume":"52","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, USI-SUPSI, Lugano-Viganello, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Afrouz Jabal","family":"Ameli","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"ref1","first-page":"19","volume":"15","author":"Adjiashvili D.","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"ref2","author":"Angelidakis H.","journal-title":"Math. Program."},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"M. Basavaraju , \nF. V. Fomin , \nP. A. Golovach , \nP. Misra , \nM. S. Ramanujan , and \nS. Saurabh , Parameterized algorithms to preserve connectivity, in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings, Part I, Copenhagen, Denmark, Springer, Berlin, 2014, pp. 800\u2013811, https:\/\/doi.org\/10.1007\/978-3-662-43948-7.","DOI":"10.1007\/978-3-662-43948-7_66"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"J. Byrka , \nF. Grandoni , and \nA. Jabal Ameli , Breaching the 2-approximation barrier for connectivity augmentation: A reduction to Steiner tree, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, \nK. Makarychev , \nY. Makarychev , \nM. Tulsiani , \nG. Kamath , and \nJ. Chuzhoy , eds. ACM, New York, 2020, pp. 815\u2013825.","DOI":"10.1145\/3357713.3384301"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"F. Cecchetto , \nV. Traub , and \nR. Zenklusen , Bridging the gap between tree and connectivity augmentation: Unified and stronger approaches, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, ACM, New York, 2021, pp. 370\u2013383, https:\/\/arxiv.org\/abs\/2012.00086.","DOI":"10.1145\/3406325.3451086"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0270-4"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0275-7"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"J. Cheriyan , \nT. Jord\u00e1n , and \nR. Ravi , On 2-coverings and 2-packings of laminar families, in Proceedings of Algorithms - ESA \u201999, 7th Annual European Symposium, Prague, Czech Republic, Springer, Berlin, 1999, pp. 510\u2013520, https:\/\/doi.org\/10.1007\/3-540-48481-7_44.","DOI":"10.1007\/3-540-48481-7_44"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.004"},{"key":"ref12","first-page":"290","volume-title":"Studies in Discrete Optimization.","author":"Dinitz E. A.","year":"1976"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497297"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"S. Fiorini , \nM. Gro\u00df , \nJ. K\u00f6nemann , and \nL. Sanit\u00e0 , Approximating weighted tree augmentation via Chv\u00e1tal-Gomory cuts, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, \nA. Czumaj , ed. New Orleans, LA, SIAM, Philadelphia, 2018, pp. 817\u2013831, https:\/\/doi.org\/10.1137\/1.9781611975031.53.","DOI":"10.1137\/1.9781611975031.53"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/080732572"},{"key":"ref17","unstructured":"M. X. Goemans , \nA. V. Goldberg , \nS. A. Plotkin , \nD. Shmoys , \n\u00c9. Tardos , and \nD. P. Williamson , Improved approximation algorithms for network design problems, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, SIAM, Philadelphia, 1994, pp. 223\u2013232, https:\/\/dl.acm.org\/doi\/10.5555\/314464.314497."},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"F. Grandoni , \nA. Jabal Ameli , and \nV. Traub , Breaching the 2-approximation barrier for the forest augmentation problem, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, ACM, New York, 2022, pp. 1598\u20131611.","DOI":"10.1145\/3519935.3520035"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"F. Grandoni , \nC. Kalaitzis , and \nR. Zenklusen , Improved approximation for tree augmentation: Saving by rewiring, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, ACM, New York, 2018, pp. 632\u2013645, https:\/\/doi.org\/10.1145\/3188745.3188898.","DOI":"10.1145\/3188745.3188898"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-10025-6"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/3341599"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2022.10.007"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"ref26","unstructured":"G. Kortsarz  and \nZ. Nutov , Lp-relaxations for tree augmentation, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, 2016, Paris, France, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2016, 13, https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.13."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/2786981"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/2700210"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"Z. Nutov , 2-node-connectivity network design, in Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Virtual Event, 2020, Revised Selected Papers, \nC. Kaklamanis , and \nA. Levin , eds. Lecture Notes in Comput. Sci. 12806, Springer, Cham, Switzerland, 2021, pp. 220\u2013235, https:\/\/doi.org\/10.1007\/978-3-030-80879-2_15.","DOI":"10.1007\/978-3-030-80879-2_15"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"Z. Nutov , Approximation algorithms for connectivity augmentation problems, in Proceeding of International Computer Science Symposium in Russia, CSR 2021, Sochi, 2021, pp. 321\u2013338, https:\/\/link.springer.com\/chapter\/10.1007\/978-3-030-79416-3_19.","DOI":"10.1007\/978-3-030-79416-3_19"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00765-9"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"V. Traub  and \nR. Zenklusen , A better-than-2 approximation for weighted tree augmentation, in IEEE 62nd Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2021, pp. 1\u201312.","DOI":"10.1109\/FOCS52979.2021.00010"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"V. Traub  and \nR. Zenklusen , Local search for weighted tree augmentation and Steiner tree, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, SIAM, Philadelphia, pp. 3253\u20133271, https:\/\/doi.org\/10.1137\/1.9781611977073.128.","DOI":"10.1137\/1.9781611977073.128"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1421143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:35Z","timestamp":1787339975000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1421143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,23]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M1421143"],"URL":"https:\/\/doi.org\/10.1137\/21m1421143","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,23]]}}}