{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:39:10Z","timestamp":1773391150428,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_184622"],"award-info":[{"award-number":["200021_184622"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["817750"],"award-info":[{"award-number":["817750"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451086","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"370-383","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Bridging the gap between tree and connectivity augmentation: unified and stronger approaches"],"prefix":"10.1145","author":[{"given":"Federica","family":"Cecchetto","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Vera","family":"Traub","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3182395"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_66"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384301"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_3_2_1_5_1","unstructured":"F. Cecchetto V. Traub and R. Zenklusen. 2020. Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches. https: \/\/arxiv.org\/abs\/ 2012.00086."},{"key":"e_1_3_2_1_6_1","unstructured":"J. Cheriyan R. Cummings J. Dippel and J. Zhu. 2020. An Improved Approximation Algorithm for the Matching Augmentation Problem. https:\/\/arxiv.org\/abs\/ 2007.11559."},{"key":"e_1_3_2_1_7_1","unstructured":"J. Cheriyan J. Dippel F. Grandoni A. Khan and V. V. Narayan. 2020. The"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"J. Cheriyan and Z. Gao. 2017. Approximating (Unweighted) Tree Augmentation via Lift-and-Project Part II. Algorithmica 80 ( 2017 ) 608-651. https:\/\/doi.org\/10. 1007\/s00453-017-0275-7 10.1007\/s00453-017-0275-7","DOI":"10.1007\/s00453-017-0275-7"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"J. Cheriyan and Z. Gao. 2018. Approximating (Unweighted) Tree Augmentation via Lift-and-Project Part I: Stemless TAP. Algorithmica 2 ( 2018 ) 530-559. https: \/\/doi.org\/10.1007\/s00453-016-0270-4 10.1007\/s00453-016-0270-4","DOI":"10.1007\/s00453-016-0270-4"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48481-7_44"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"N. Cohen and Z. Nutov. 2013. A (1+ln 2)-Approximation Algorithm for MinimumCost 2-Edge-Connectivity Augmentation of Trees with Constant Radius. Theoretical Computer Science 489 ( 2013 ) 67-74. https:\/\/doi.org\/10.1016\/j.tcs. 2013. 04.004 10.1016\/j.tcs.2013.04.004","DOI":"10.1016\/j.tcs"},{"key":"e_1_3_2_1_13_1","unstructured":"E. A. Dinitz A. V. Karzanov and M. V. Lomonosov. 1976. On the Structure of the System of Minimum Edge cuts of a Graph. Studies in Discrete Optimization (A.A. Fridman ed.) ( 1976 ) 290-306."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.53"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39479-0_10"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, USA, 223-232","author":"Goemans M. X.","unstructured":"M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, \u00c9. Tardos, and D. P. Williamson. 1994. Improved Approximation Algorithms for Network Design Problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, USA, 223-232."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188898"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"F. Grandoni C. Kalaitzis and R. Zenklusen. 2018. Improved Approximations for Tree Augmentation: Saving by Rewiring. https:\/\/arxiv.org\/abs\/ 1804.02242.","DOI":"10.1145\/3188745.3188898"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341599"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","unstructured":"K. Jain. 2001. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica 21 ( 2001 ) 39-60. https:\/\/doi.org\/10.1007\/ s004930170004 10.1007\/s004930170004","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786981"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"G. Kortsarz and Z. Nutov. 2018. LP-Relaxations for Tree Augmentation. Discrete Applied Mathematics 239 ( 2018 ) 94-105. https:\/\/doi.org\/10.1016\/j.dam. 2017. 12. 033 10.1016\/j.dam.2017.12.033","DOI":"10.1016\/j.dam"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"L. C. Lau R. Ravi and M. Singh. 2011. Iterative Methods in Combinatorial Optimization (1st ed.). Cambridge University Press New York NY USA. https: \/\/doi.org\/10.1017\/CBO9780511977152 10.1017\/CBO9780511977152","DOI":"10.1017\/CBO9780511977152"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","unstructured":"H. Nagamochi. 2003. An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree. Discrete Applied Mathematics 126 1 ( 2003 ) 83-113. https:\/\/doi.org\/10.1016\/ S0166-218X( 02 ) 00218-4 10.1016\/S0166-218X(02)00218-4","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA"},{"key":"e_1_3_2_1_33_1","volume-title":"Approximation Algorithms for Connectivity Augmentation Problems. https:\/\/arxiv.org\/abs\/","author":"Nutov Z.","year":"2009","unstructured":"Z. Nutov. 2020. Approximation Algorithms for Connectivity Augmentation Problems. https:\/\/arxiv.org\/abs\/ 2009.13257."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"A. Seb\u0151 and J. Vygen. 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. Combinatorica 34 5 ( 2014 ) 597-629. https:\/\/doi.org\/10.1007\/s00493-014-2960-3 10.1007\/s00493-014-2960-3","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"D. P. Williamson and D. B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press Cambridge. https:\/\/doi.org\/10.1017\/ CBO9780511921735 10.1017\/CBO9780511921735","DOI":"10.1017\/CBO9780511921735"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451086","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":35,"alternative-id":["10.1145\/3406325.3451086","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451086","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}