{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T23:51:05Z","timestamp":1784850665567,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Swiss National Science Foundation","award":["200021_184622"],"award-info":[{"award-number":["200021_184622"]}]},{"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":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585122","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1820-1833","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A (1.5+\u03b5)-Approximation Algorithm for Weighted Connectivity Augmentation"],"prefix":"10.1145","author":[{"given":"Vera","family":"Traub","sequence":"first","affiliation":[{"name":"University of Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_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, 19 : 1-19 : 26. doi: 10.1145\/3182395. 10.1145\/3182395 D. Adjiashvili. 2018. Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Transactions on Algorithms, 15, 2, 19 : 1-19 : 26. doi: 10.1145\/3182395.","journal-title":"ACM Transactions on Algorithms"},{"key":"#cr-split#-e_1_3_2_1_2_1.1","doi-asserted-by":"crossref","unstructured":"H. Angelidakis D. Hyatt-Denesik and L. Sanit\u00e1. 2022. Node connectivity augmentation via iterative randomized rounding. Mathematical Programming. doi: 10.1007\/s10107-022-01854-z. 10.1007\/s10107-022-01854-z","DOI":"10.1007\/s10107-022-01854-z"},{"key":"#cr-split#-e_1_3_2_1_2_1.2","doi-asserted-by":"crossref","unstructured":"H. Angelidakis D. Hyatt-Denesik and L. Sanit\u00e1. 2022. Node connectivity augmentation via iterative randomized rounding. Mathematical Programming. doi: 10.1007\/s10107-022-01854-z.","DOI":"10.1007\/s10107-022-01854-z"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), 57-69","author":"Drygala M.","unstructured":"\u00c9. Bamas, M. Drygala , and O. Svensson . 2022. A simple LP-based approximation algorithm for the matching augmentation problem . In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), 57-69 . doi: 10.1007\/978-3-031-06901-7_5. 10.1007\/978-3-031-06901-7_5 \u00c9. Bamas, M. Drygala, and O. Svensson. 2022. A simple LP-based approximation algorithm for the matching augmentation problem. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), 57-69. doi: 10.1007\/978-3-031-06901-7_5."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 800-811","year":"2014","unstructured":"Saurabh. 2014 . Parameterized algorithms to preserve connectivity . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 800-811 . doi: 10.1007\/978-3-662-43948-7_66. 10.1007\/978-3-662-43948-7_66 Saurabh. 2014. Parameterized algorithms to preserve connectivity. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 800-811. doi: 10.1007\/978-3-662-43948-7_66."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). doi: 10","author":"Byrka J.","unstructured":"J. Byrka , F. Grandoni , and A. Jabal Ameli . 2020. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree . In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). doi: 10 .1145\/335 7713.3384301. 10.1145\/335 J. Byrka, F. Grandoni, and A. Jabal Ameli. 2020. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC). doi: 10.1145\/335 7713.3384301."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 370-383","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 the 53rd Annual ACM Symposium on Theory of Computing (STOC), 370-383 . F. Cecchetto, V. Traub, and R. Zenklusen. 2021. Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 370-383."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"doi: 10.1145\/3406325.3451086. \t\t\t\t    10.1145\/3406325.3451086\ndoi: 10.1145\/3406325.3451086.","DOI":"10.1145\/3406325.3451086"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1453505"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01394-z"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0270-4"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0275-7"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.01.009"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"doi: 10.1137\/S009753979833920X. \t\t\t\t    10.1137\/S009753979833920X\ndoi: 10.1137\/S009753979833920X.","DOI":"10.1137\/S009753979833920X"},{"key":"e_1_3_2_1_15_1","unstructured":"N. Cohen and Z. Nutov. 2013. A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius. \t\t\t\t  N. Cohen and Z. Nutov. 2013. A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius."},{"key":"e_1_3_2_1_16_1","volume-title":"doi: 10.1016\/j.tcs","year":"2013","unstructured":"Theoretical Computer Science, 489, 67-74. doi: 10.1016\/j.tcs . 2013 . 04.004. 10.1016\/j.tcs Theoretical Computer Science, 489, 67-74. doi: 10.1016\/j.tcs. 2013. 04.004."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"J. Davies and R. McCarty. 2021. Circle graphs are quadratically-bounded. \t\t\t\t  J. Davies and R. McCarty. 2021. Circle graphs are quadratically-bounded.","DOI":"10.1112\/blms.12447"},{"key":"e_1_3_2_1_18_1","unstructured":"Bulletin of the London Mathematical Society 53 673-679. doi: 10.1112\/blms.124 47. \t\t\t\t    10.1112\/blms.124\nBulletin of the London Mathematical Society 53 673-679. doi: 10.1112\/blms.124 47."},{"key":"e_1_3_2_1_19_1","first-page":"290","article-title":"On the structure of the system of minimum edge cuts of a graph","author":"Dinitz E. A.","year":"1976","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 , 290 - 306 . 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, 290-306.","journal-title":"Studies in Discrete Optimization"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497297"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 817-831","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-831 . doi: 10.1137\/1.9781611975031.53. 10.1137\/1.9781611975031.53 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-831. doi: 10.1137\/1.9781611975031.53."},{"key":"e_1_3_2_1_22_1","unstructured":"A. Frank and \u00c9. Tardos. 1989. An application of submodular flows. Linear Algebra and its Applications 114-115 329-348. doi: 10.1016\/ 0024-3795 ( 89 )9046 9-2. \t\t\t\t  A. Frank and \u00c9. Tardos. 1989. An application of submodular flows. Linear Algebra and its Applications 114-115 329-348. doi: 10.1016\/ 0024-3795 ( 89 )9046 9-2."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"doi: 10.1137\/0210019. \t\t\t\t    10.1137\/0210019\ndoi: 10.1137\/0210019.","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 234-243","author":"Gabow H. N.","year":"2004","unstructured":"H. N. Gabow . 2004 . Special edges, and approximating the smallest directed-edge connected subgraph . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 234-243 . H. N. Gabow. 2004. Special edges, and approximating the smallest directed-edge connected subgraph. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 234-243."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"H. N. Gabow M. X. Goemans \u00c9. Tardos and D. P. Williamson. 2009. Approximating the smallest-edge connected spanning subgraph by lp-rounding. \t\t\t\t  H. N. Gabow M. X. Goemans \u00c9. Tardos and D. P. Williamson. 2009. Approximating the smallest-edge connected spanning subgraph by lp-rounding.","DOI":"10.1002\/net.20289"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Networks 53 4 345-357. doi: 10.1002\/net.20289. \t\t\t\t    10.1002\/net.20289\nNetworks 53 4 345-357. doi: 10.1002\/net.20289.","DOI":"10.1002\/net.20289"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-10025-6"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"#cr-split#-e_1_3_2_1_30_1.1","unstructured":"M. Garg F. Hommelsheim and N. Megow. 2022. Matching augmentation via simultaneous contractions. ( 2022 ). doi: 10.48550\/arXiv.2211. 01912. 10.48550\/arXiv.2211"},{"key":"#cr-split#-e_1_3_2_1_30_1.2","unstructured":"M. Garg F. Hommelsheim and N. Megow. 2022. Matching augmentation via simultaneous contractions. ( 2022 ). doi: 10.48550\/arXiv.2211. 01912."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 223-232","year":"1994","unstructured":"Williamson. 1994 . Improved approximation algorithms for network design problems . In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 223-232 . Williamson. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 223-232."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 1598-1611","author":"Grandoni F.","unstructured":"F. Grandoni , A. Jabal Ameli , and V. Traub . 2022. Breaching the 2-approximation barrier for the forest augmentation problem . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 1598-1611 . doi: 10.1145\/3519935.3520035. 10.1145\/3519935.3520035 F. Grandoni, A. Jabal Ameli, and V. Traub. 2022. Breaching the 2-approximation barrier for the forest augmentation problem. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 1598-1611. doi: 10.1145\/3519935.3520035."},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of 50th ACM Symposium on Theory of Computing (STOC), 632-645","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-645 . doi: 10.1145\/3188745.3188898. 10.1145\/3188745.3188898 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-645. doi: 10.1145\/3188745.3188898."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90044-5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"J. M. Keil. 1993. The complexity of domination problems in circle graphs. \t\t\t\t  J. M. Keil. 1993. The complexity of domination problems in circle graphs.","DOI":"10.1016\/0166-218X(93)90178-Q"},{"key":"e_1_3_2_1_38_1","unstructured":"Discrete Applied Mathematics 42 51-63. doi: 10.1016\/ 0166-218X ( 93 ) 90178-Q. \t\t\t\t  Discrete Applied Mathematics 42 51-63. doi: 10.1016\/ 0166-218X ( 93 ) 90178-Q."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1010"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000099"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786981"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.033"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00218-4"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.05.016"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79416-3_19"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of 25th Annual Symposium on Algorithms (ESA), 61 : 1-61 : 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-61 : 14 . doi: 10.1007\/s00453-020-00765-9. 10.1007\/s00453-020-00765-9 Z. Nutov. 2017. On the tree augmentation problem. In Proceedings of 25th Annual Symposium on Algorithms (ESA), 61 : 1-61 : 14. doi: 10.1007\/s00453-020-00765-9."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1012"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9830-z"},{"key":"e_1_3_2_1_50_1","unstructured":"V. Traub and R. Zenklusen. 2022. A (1.5 + )-approximation algorithm for weighted connectivity augmentation. https:\/\/arxiv.org\/abs\/2209.07860. ( 2022 ). \t\t\t\t  V. Traub and R. Zenklusen. 2022. A (1.5 + )-approximation algorithm for weighted connectivity augmentation. https:\/\/arxiv.org\/abs\/2209.07860. ( 2022 )."},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS), 1-12","author":"Traub V.","unstructured":"V. Traub and R. Zenklusen . 2021. A better-than-2 approximation algorithm for weighted tree augmentation . In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS), 1-12 . doi: 10.1109\/FOCS52979.202 1.00010. 10.1109\/FOCS52979.202 V. Traub and R. Zenklusen. 2021. A better-than-2 approximation algorithm for weighted tree augmentation. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS), 1-12. doi: 10.1109\/FOCS52979.202 1.00010."},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, 3253-3272","author":"Traub V.","unstructured":"V. Traub and R. Zenklusen . 2022. Local search for weighted tree augmentation and Steiner tree . In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, 3253-3272 . doi: 10.1137\/1.9781611977073.128. 10.1137\/1.9781611977073.128 V. Traub and R. Zenklusen. 2022. Local search for weighted tree augmentation and Steiner tree. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, 3253-3272. doi: 10.1137\/1.9781611977073.128."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035832"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"doi: 10.1007\/BFb0035832. \t\t\t\t    10.1007\/BFb0035832\ndoi: 10.1007\/BFb0035832.","DOI":"10.1007\/BFb0035832"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":56,"alternative-id":["10.1145\/3564246.3585122","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585122","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}