{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:22:49Z","timestamp":1771485769005,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520062","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1612-1620","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An improved approximation algorithm for the minimum\n            <i>k<\/i>\n            -edge connected multi-subgraph problem"],"prefix":"10.1145","author":[{"given":"Anna R.","family":"Karlin","sequence":"first","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Klein","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shayan Oveis","family":"Gharan","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Shayan Oveis Gharan, and Amin Saberi","author":"Asadpour Arash","year":"2017","unstructured":"Arash Asadpour , Michel X. Goemans , Aleksander Mdry , Shayan Oveis Gharan, and Amin Saberi . 2017 . An O (log n \/log log n )-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Operations Research , 65, 4 (2017). Arash Asadpour, Michel X. Goemans, Aleksander Mdry, Shayan Oveis Gharan, and Amin Saberi. 2017. An O (log n \/log log n )-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Operations Research, 65, 4 (2017)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00618-8"},{"key":"e_1_3_2_1_3_1","unstructured":"Sylvia Boyd Joseph Cheriyan Robert Cummings Logan Grout Sharat Ibrahimpur Zolt\u00e1n Szigeti and Lu Wang. 2020. A 4\/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In APPROX\/RANDOM Jaros\u0142 aw Byrka and Raghu Meka (Eds.). 176 Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik 61:1\u201361:12.  Sylvia Boyd Joseph Cheriyan Robert Cummings Logan Grout Sharat Ibrahimpur Zolt\u00e1n Szigeti and Lu Wang. 2020. A 4\/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In APPROX\/RANDOM Jaros\u0142 aw Byrka and Raghu Meka (Eds.). 176 Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik 61:1\u201361:12."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.014"},{"key":"e_1_3_2_1_5_1","volume-title":"Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree","author":"Byrka Jaroslaw","unstructured":"Jaroslaw Byrka , Fabrizio Grandoni , and Afrouz Jabal Ameli . 2020. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree . In STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM , 815\u2013825. Jaroslaw Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli. 2020. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. In STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, 815\u2013825."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Robert Carr and R. Ravi. 1998. A New Bound for the 2-Edge Connected Subgraph Problem. In IPCO Robert E. Bixby E. Andrew Boyd and Roger Z. R\u00edos-Mercado (Eds.). Springer Berlin Heidelberg Berlin Heidelberg. 112\u2013125.  Robert Carr and R. Ravi. 1998. A New Bound for the 2-Edge Connected Subgraph Problem. In IPCO Robert E. Bixby E. Andrew Boyd and Roger Z. R\u00edos-Mercado (Eds.). Springer Berlin Heidelberg Berlin Heidelberg. 112\u2013125.","DOI":"10.1007\/3-540-69346-7_9"},{"key":"e_1_3_2_1_7_1","volume-title":"Bridging the gap between tree and connectivity augmentation: unified and stronger approaches","author":"Cecchetto Federica","unstructured":"Federica Cecchetto , Vera Traub , and Rico Zenklusen . 2021. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches . In STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM , 370\u2013383. Federica Cecchetto, Vera Traub, and Rico Zenklusen. 2021. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 370\u2013383."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Jan Vondr\u00e1k and Rico Zenklusen. 2010. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In FOCS. 575\u2013584.  Chandra Chekuri Jan Vondr\u00e1k and Rico Zenklusen. 2010. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In FOCS. 575\u2013584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_3_2_1_10_1","volume-title":"Combinatorial Structures and Their Applications. Gordon and Breach","author":"Edmonds Jack","unstructured":"Jack Edmonds . 1970. Submodular functions, matroids and certain polyhedra . In Combinatorial Structures and Their Applications. Gordon and Breach , New York, NY, USA . 69\u201387. Jack Edmonds. 1970. Submodular functions, matroids and certain polyhedra. In Combinatorial Structures and Their Applications. Gordon and Breach, New York, NY, USA. 69\u201387."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Samuel Fiorini Martin Gro\u00df Jochen K\u00f6nemann and Laura Sanit\u00e0. 2018. Approximating Weighted Tree Augmentation via Chv\u00e1tal-Gomory Cuts. In SODA. 817\u2013831.  Samuel Fiorini Martin Gro\u00df Jochen K\u00f6nemann and Laura Sanit\u00e0. 2018. Approximating Weighted Tree Augmentation via Chv\u00e1tal-Gomory Cuts. In SODA. 817\u2013831.","DOI":"10.1137\/1.9781611975031.53"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90059-7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102414910"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080732572"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1541872.1541876"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112670.3113039"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728178"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Anna Karlin Nathan Klein and Shayan Oveis Gharan. 2021. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. arxiv:2105.10043.  Anna Karlin Nathan Klein and Shayan Oveis Gharan. 2021. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. arxiv:2105.10043.","DOI":"10.1109\/FOCS54457.2022.00084"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Anna R. Karlin Nathan Klein and Shayan Oveis Gharan. 2021. A (Slightly) Improved Approximation Algorithm for Metric TSP. In STOC. ACM.  Anna R. Karlin Nathan Klein and Shayan Oveis Gharan. 2021. A (Slightly) Improved Approximation Algorithm for Metric TSP. In STOC. ACM.","DOI":"10.1145\/3406325.3451009"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0052"},{"key":"e_1_3_2_1_23_1","volume-title":"Shayan Oveis Gharan, and Mohit Singh","author":"Laekhanukit Bundit","year":"2012","unstructured":"Bundit Laekhanukit , Shayan Oveis Gharan, and Mohit Singh . 2012 . A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. In ICALP, Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.) (Lecture Notes in Computer Science , Vol. 7391). Springer, 606\u2013 616 . Bundit Laekhanukit, Shayan Oveis Gharan, and Mohit Singh. 2012. A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. In ICALP, Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.) (Lecture Notes in Computer Science, Vol. 7391). Springer, 606\u2013616."},{"key":"e_1_3_2_1_24_1","volume-title":"A Randomized Rounding Approach to the Traveling Salesman Problem","author":"Gharan Shayan Oveis","unstructured":"Shayan Oveis Gharan , Amin Saberi , and Mohit Singh . 2011. A Randomized Rounding Approach to the Traveling Salesman Problem . In FOCS. IEEE Computer Society , 550\u2013559. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2011. A Randomized Rounding Approach to the Traveling Salesman Problem. In FOCS. IEEE Computer Society, 550\u2013559."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2747"},{"key":"e_1_3_2_1_26_1","volume-title":"k-Edge-Connectivity: Approximation and LP Relaxation","author":"Pritchard David","unstructured":"David Pritchard . 2011. k-Edge-Connectivity: Approximation and LP Relaxation . In Approximation and Online Algorithms, Klaus Jansen and Roberto Solis-Oba (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 225\u2013236. David Pritchard. 2011. k-Edge-Connectivity: Approximation and LP Relaxation. In Approximation and Online Algorithms, Klaus Jansen and Roberto Solis-Oba (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 225\u2013236."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Vera Traub and Rico Zenklusen. 2021. A Better-Than-2 Approximation for Weighted Tree Augmentation. to appear  Vera Traub and Rico Zenklusen. 2021. A Better-Than-2 Approximation for Weighted Tree Augmentation. to appear","DOI":"10.1109\/FOCS52979.2021.00010"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520062","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":28,"alternative-id":["10.1145\/3519935.3520062","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520062","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}