{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T03:52:30Z","timestamp":1770349950370,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NCN","award":["2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2015\/18\/E\/ST6\/00456"]}]},{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200020B\\_182865\/1"],"award-info":[{"award-number":["200020B\\_182865\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384301","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"815-825","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree"],"prefix":"10.1145","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, Switzerland"}]},{"given":"Afrouz Jabal","family":"Ameli","sequence":"additional","affiliation":[{"name":"IDSIA, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.157"},{"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\/2432622.2432628"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0270-4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0275-7"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48481-7_44"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.004"},{"key":"e_1_3_2_1_9_1","unstructured":"E. A. Dinits A. V. Karzanov and M. V. Lomonosov. 1976. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization ( 1976 ) 290-306.  E. A. Dinits A. V. Karzanov and M. V. Lomonosov. 1976. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization ( 1976 ) 290-306."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497297"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","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.1137\/080732572"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39479-0_10"},{"key":"e_1_3_2_1_15_1","first-page":"223","volume-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Goemans Michel X.","year":"1994","unstructured":"Michel X. Goemans , Andrew V. Goldberg , Serge A. Plotkin , David B. Shmoys , \u00c9va Tardos , and David P. Williamson . 1994. Improved Approximation Algorithms for Network Design Problems . In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994 . ACM\/SIAM, Arlington, Virginia, USA , 223 - 232 . http:\/\/dl.acm.org\/citation.cfm?id= 314464. 314497 Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, \u00c9va Tardos, and David P. Williamson. 1994. Improved Approximation Algorithms for Network Design Problems. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994. ACM\/SIAM, Arlington, Virginia, USA, 223-232. http:\/\/dl.acm.org\/citation.cfm?id= 314464. 314497"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188898"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341599"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kamal Jain. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21 1 ( 2001 ) 39-60.  Kamal Jain. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21 1 ( 2001 ) 39-60.","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.13"},{"key":"e_1_3_2_1_22_1","article-title":"A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2","volume":"12","author":"Kortsarz G.","year":"2016","unstructured":"G. Kortsarz and Z. Nutov . 2016 . A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2 . ACM Transactions on Algorithms (TALG) 12 , 2 ( 2016 ), 23 : 1-23 : 20. G. Kortsarz and Z. Nutov. 2016. A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2. ACM Transactions on Algorithms (TALG) 12, 2 ( 2016 ), 23 : 1-23 : 20.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700210"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","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.  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.","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2017.61"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Seb\u00f6 and Jens Vygen. 2014. Shorter Tours by Nicer Ears: 7\/5-approximation for graphic TSP 3\/2 for the path version and 4\/3 for two-edgeconnected subgraphs. Combinatorica 34 ( 5 ) ( 2014 ) 597-629. arXiv: 1201. 1870 http:\/\/arxiv.org\/abs\/1201.1870  Andr\u00e1s Seb\u00f6 and Jens Vygen. 2014. Shorter Tours by Nicer Ears: 7\/5-approximation for graphic TSP 3\/2 for the path version and 4\/3 for two-edgeconnected subgraphs. Combinatorica 34 ( 5 ) ( 2014 ) 597-629. arXiv: 1201. 1870 http:\/\/arxiv.org\/abs\/1201.1870","DOI":"10.1007\/s00493-014-2960-3"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":27,"alternative-id":["10.1145\/3357713.3384301","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384301","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}