{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005693,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","funder":[{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200021_200731 \\\/ 1"],"award-info":[{"award-number":["200021_200731 \\\/ 1"]}]},{"name":"CSR Grant","award":["WMGT-23-0001"],"award-info":[{"award-number":["WMGT-23-0001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718275","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"653-664","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A 5\/4-Approximation for Two-Edge Connectivity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8647-6928","authenticated-orcid":false,"given":"Miguel","family":"Bosch-Calvo","sequence":"first","affiliation":[{"name":"IDSIA at USI-SUPSI, Lugano, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1230-4821","authenticated-orcid":false,"given":"Mohit","family":"Garg","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bengaluru, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9676-4931","authenticated-orcid":false,"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA at USI-SUPSI, Lugano, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4444-9793","authenticated-orcid":false,"given":"Felix","family":"Hommelsheim","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5620-9039","authenticated-orcid":false,"given":"Afrouz Jabal","family":"Ameli","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6714-5034","authenticated-orcid":false,"given":"Alexander","family":"Lindermayr","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,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\/S10107-022-01854-Z"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06901-7_5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2408.07019"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.29"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1421143"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Federica Cecchetto Vera Traub and Rico Zenklusen. 2021. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In STOC. ACM 370\u2013383. https:\/\/doi.org\/10.1145\/3406325.3451086 10.1145\/3406325.3451086","DOI":"10.1145\/3406325.3451086"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2022.37"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1453505"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10107-019-01394-Z"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-016-0270-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-017-0275-7"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199362071"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2013.04.004"},{"volume-title":"On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem","author":"Czumaj Artur","key":"e_1_3_2_1_16_1","unstructured":"Artur Czumaj and Andrzej Lingas. 1999. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem. In SODA. ACM\/SIAM, 281\u2013290. http:\/\/dl.acm.org\/citation.cfm?id=314500.314573"},{"key":"e_1_3_2_1_17_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 290\u2013306."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497297"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/JAGM.1998.0931"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.53"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/080732572"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/NET.20289"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-020-10025-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH92"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.65"},{"volume-title":"Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques","author":"Garg Naveen","key":"e_1_3_2_1_26_1","unstructured":"Naveen Garg, Santosh S. Vempala, and Aman Singla. 1993. Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques. In SODA. ACM\/SIAM, 103\u2013111. http:\/\/dl.acm.org\/citation.cfm?id=313559.313618"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520035"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Fabrizio Grandoni Christos Kalaitzis and Rico Zenklusen. 2018. Improved approximation for tree augmentation: saving by rewiring. In STOC. ACM 632\u2013645. https:\/\/doi.org\/10.1145\/3188745.3188898 10.1145\/3188745.3188898","DOI":"10.1145\/3188745.3188898"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091587"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341599"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/S004930170004"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Samir Khuller and Uzi Vishkin. 1992. Biconnectivity Approximations and Graph Carvings. In STOC. ACM 759\u2013770. https:\/\/doi.org\/10.1145\/129712.129786 10.1145\/129712.129786","DOI":"10.1145\/129712.129786"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ISAAC.2023.49"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786981"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.DAM.2017.12.033"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-020-00765-9"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.114367"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00493-014-2960-3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00010"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.128"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585122"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:46Z","timestamp":1750693666000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":42,"alternative-id":["10.1145\/3717823.3718275","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718275","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}