{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:35Z","timestamp":1781345675018,"version":"3.54.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2025,3,16]],"date-time":"2025-03-16T00:00:00Z","timestamp":1742083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"abstract":"<jats:p>\n            We present the first approximation algorithms for the Weighted Tree Augmentation Problem (WTAP) that beat the longstanding approximation factor of 2, which can be achieved through standard techniques. The core of our approach is a novel decomposition theorem based on a well-chosen class of\n            <jats:italic>thin components<\/jats:italic>\n            . The decomposition theorem asserts that for any pair of a highly structured (but potentially expensive) WTAP solution and a cheaper WTAP solution, there is a way to decompose the cheaper solution into thin components, one of which allows for improving the structured solution. Together with the fact that we can efficiently optimize over thin components through a dynamic program, our decomposition theorem leads to a relative greedy algorithm for WTAP that is a (1 + ln\u20092 + \u03f5)-approximation.\n          <\/jats:p>\n          <jats:p>Moreover, we present an approach to improve on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. The main application of this approach leads to a (1.5 + \u03f5)-approximation for WTAP. Furthermore, for the Steiner Tree Problem, it provides an alternative way to obtain the currently best known approximation factor of ln\u20094 + \u03f5. Contrary to prior methods, our approach is purely combinatorial without the need to solve an LP. Nevertheless, the solution value can still be bounded in terms of the well-known hypergraphic LP, leading to an alternative, and arguably simpler, way to bound its integrality gap by ln\u20094.<\/jats:p>","DOI":"10.1145\/3722101","type":"journal-article","created":{"date-parts":[[2025,3,16]],"date-time":"2025-03-16T09:35:26Z","timestamp":1742117726000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9749-2600","authenticated-orcid":false,"given":"Vera","family":"Traub","sequence":"first","affiliation":[{"name":"University of Bonn,  Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7148-9304","authenticated-orcid":false,"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich,  Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,3,16]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs","volume":"15","author":"Adjiashvili D.","year":"2018","unstructured":"D. Adjiashvili. 2018. Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs. ACM Transactions on Algorithms 15, 2 (2018), 19:1\u201319:26.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06901-7_5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of 52nd ACM Symposium on Theory of Computing (STOC).","author":"Byrka J.","unstructured":"J. Byrka, F. Grandoni, and A. Jabal\u00a0Ameli. 2020. Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree. In Proceedings of 52nd ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of 53rd Annual ACM Symposium on Theory of Computing (STOC). 370\u2013383","author":"Cecchetto F.","unstructured":"F. Cecchetto, V. Traub, and R. Zenklusen. 2021. Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches. In Proceedings of 53rd Annual ACM Symposium on Theory of Computing (STOC). 370\u2013383."},{"key":"e_1_2_1_7_1","unstructured":"J. Cheriyan R. Cummings J. Dippel and J. Zhu. 2020. An Improved Approximation Algorithm\u00a0for the Matching Augmentation Problem. https:\/\/arxiv.org\/abs\/2007.11559."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01394-z"},{"key":"e_1_2_1_9_1","first-page":"530","article-title":"Approximating (Unweighted) Tree Augmentation via Lift-and-Project","volume":"80","author":"Cheriyan J.","year":"2018","unstructured":"J. Cheriyan and Z. Gao. 2018. Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica 80(2018), 530\u2013559.","journal-title":"Part I: Stemless TAP. Algorithmica"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0275-7"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of 7th Annual European Symposium on Algorithms (ESA). 510\u2013520","author":"Cheriyan J.","unstructured":"J. Cheriyan, T. Jord\u00e1n, and R. Ravi. 1999. On 2-Coverings and 2-Packings of Laminar Families. In Proceedings of 7th Annual European Symposium on Algorithms (ESA). 510\u2013520."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.01.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185402"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497297"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 817\u2013831","author":"Fiorini S.","unstructured":"S. Fiorini, M. Gro\u00df, J. K\u00f6nemann, and L. Sanit\u00e0. 2018. Approximating Weighted Tree Augmentation via Chv\u00e1tal-Gomory Cuts. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 817\u2013831."},{"key":"e_1_2_1_19_1","volume-title":"An Application of Submodular Flows. Linear Algebra Appl. 114\u2013115","author":"Frank A.","year":"1989","unstructured":"A. Frank and \u00c9. Tardos. 1989. An Application of Submodular Flows. Linear Algebra Appl. 114\u2013115 (1989), 329\u2013348."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 234\u2013243","author":"Gabow N.","year":"2004","unstructured":"H.\u00a0N. Gabow. 2004. Special Edges, and Approximating the Smallest Directed k-Edge Connected Subgraph. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 234\u2013243."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20289"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"M. Garg F. Hommelsheim and N. Megow. 2022. Matching Augmentation via Simultaneous Contractions. https:\/\/doi.org\/10.48550\/arXiv.2211.01912. doi: 10.48550\/arXiv.2211.01912","DOI":"10.48550\/arXiv.2211.01912"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 223\u2013232","author":"Goemans X.","year":"1994","unstructured":"M.\u00a0X. Goemans, A.\u00a0V. Goldberg, S. Plotkin, D.\u00a0B. Shmoys, \u00c9. Tardos, and D.\u00a0P. Williamson. 1994. Improved Approximation Algorithms for Network Design Problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 223\u2013232."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 44th ACM Symposium on Theory of Computing (STOC). ACM","author":"Goemans X.","unstructured":"M.\u00a0X. Goemans, N. Olver, T. Rothvo\u00df, and R. Zenklusen. 2012. Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations. In Proceedings of 44th ACM Symposium on Theory of Computing (STOC). ACM, New York, NY, USA, 1161\u20131175."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520035"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of 50th ACM Symposium on Theory of Computing (STOC). 632\u2013645","author":"Grandoni F.","unstructured":"F. Grandoni, C. Kalaitzis, and R. Zenklusen. 2018. Improved Approximation for Tree Augmentation: Saving by Rewiring. In Proceedings of 50th ACM Symposium on Theory of Computing (STOC). 632\u2013645."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0129045"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0255-1_7"},{"key":"e_1_2_1_30_1","unstructured":"J. Iglesias and R. Ravi. 2018. Coloring Down: 3\/2-approximation for special cases of the weighted tree augmentation problem. https:\/\/arxiv.org\/abs\/1707.05240."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520062"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 937\u2013938","author":"Khuller S.","unstructured":"S. Khuller, B. Raghavachari, and A. Zhu. 1999. A Uniform Framework for Approximating Weighted Connectivity Problems. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 937\u2013938."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416736"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786981"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.033"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.414"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of 25th Annual Symposium on Algorithms (ESA). 61:1\u201361:14","author":"Nutov Z.","year":"2017","unstructured":"Z. Nutov. 2017. On the Tree Augmentation Problem. In Proceedings of 25th Annual Symposium on Algorithms (ESA). 61:1\u201361:14."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79416-3_19"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS). 20:1\u201320:14","author":"Nutov Z.","unstructured":"Z. Nutov, G. Kortsarz, and E. Shalom. 2019. Approximating Activation Edge-Cover and Facility Location Problems. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS). 20:1\u201320:14."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch94"},{"key":"e_1_2_1_46_1","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver. 2003. Combinatorial Optimization, Polyhedra and Efficiency. Springer, Berlin Heidelberg New York."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00010"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.128"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585122"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3722101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3722101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:50Z","timestamp":1750272230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3722101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,16]]},"references-count":49,"alternative-id":["10.1145\/3722101"],"URL":"https:\/\/doi.org\/10.1145\/3722101","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,16]]},"assertion":[{"value":"2023-08-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3722101"}}