{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:35Z","timestamp":1781345675785,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council","award":["817750"],"award-info":[{"award-number":["817750"]}]},{"name":"National Science Foundation","award":["DMS=1926686, DGE-1762114, CCF-1813135"],"award-info":[{"award-number":["DMS=1926686, DGE-1762114, CCF-1813135"]}]},{"name":"Swiss National Science Foundation","award":["200021_184622"],"award-info":[{"award-number":["200021_184622"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649715","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1853-1864","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Ghost Value Augmentation for k-Edge-Connectivity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0862-3715","authenticated-orcid":false,"given":"D. Ellis","family":"Hershkowitz","sequence":"first","affiliation":[{"name":"Brown University, Providence, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4052-5864","authenticated-orcid":false,"given":"Nathan","family":"Klein","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7148-9304","authenticated-orcid":false,"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","article-title":"Beating approximation factor two for weighted tree augmentation with bounded costs","volume":"15","author":"Adjiashvili David","year":"2018","unstructured":"David Adjiashvili. 2018. Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Transactions on Algorithms (TALG), 15, 2 (2018), 1\u201326.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_2_1","first-page":"995","article-title":"Node Connectivity Augmentation via Iterative Randomized Rounding. Mathematical Programming","volume":"199","author":"Angelidakis H.","year":"2023","unstructured":"H. Angelidakis, D. Hyatt-Denesik, and L.j Sanit\u00e1. 2023. Node Connectivity Augmentation via Iterative Randomized Rounding. Mathematical Programming, Series A, 199 (2023), 995\u20131031.","journal-title":"Series A"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1006"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9 Berger and Michelangelo Grigni. 2007. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In International Colloquium on Automata Languages and Programming (ICALP). 90\u2013101.","DOI":"10.1007\/978-3-540-73420-8_10"},{"key":"e_1_3_2_1_5_1","volume-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 176","author":"Boyd Sylvia","year":"2020","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 International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 176, 61:1\u201361:12."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.014"},{"key":"e_1_3_2_1_7_1","volume-title":"Conference on Integer Programming and Combinatorial Optimization (IPCO). 112\u2013125","author":"Carr Robert","unstructured":"Robert Carr and R. Ravi. 1998. A New Bound for the 2-Edge Connected Subgraph Problem. In Conference on Integer Programming and Combinatorial Optimization (IPCO). 112\u2013125."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Federica Cecchetto Vera Traub and Rico Zenklusen. 2021. Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches. 370\u2013383.","DOI":"10.1145\/3406325.3451086"},{"key":"e_1_3_2_1_9_1","unstructured":"Parinya Chalermsook Chien-Chung Huang Danupon Nanongkai Thatchaphol Saranurak Pattara Sukprasert and Sorrachai Yingchareonthawornchai. 2022. Approximating k-edge-connected spanning subgraphs via a near-linear time LP solver. arXiv preprint arXiv:2205.14978."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9115-5"},{"key":"e_1_3_2_1_11_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC). 363\u2013372","author":"Chekuri Chandra","year":"2004","unstructured":"Chandra Chekuri, Ashish Goel, Sanjeev Khanna, and Amit Kumar. 2004. Multi-processor scheduling to minimize flow time with \u03b5 resource augmentation. In Annual ACM Symposium on Theory of Computing (STOC). 363\u2013372."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0270-4"},{"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":"publisher","DOI":"10.1137\/120902847"},{"key":"e_1_3_2_1_15_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 4, 496\u2013505","author":"Czumaj Artur","year":"2004","unstructured":"Artur Czumaj, Michelangelo Grigni, Papa A Sissokho, and Hairong Zhao. 2004. Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 4, 496\u2013505."},{"key":"e_1_3_2_1_16_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 99","author":"Czumaj Artur","year":"1999","unstructured":"Artur Czumaj and Andrzej Lingas. 1999. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem.. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 99, 281\u2013290."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212760"},{"key":"e_1_3_2_1_18_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 817\u2013831","author":"Fiorini Samuel","year":"2018","unstructured":"Samuel Fiorini, Martin Gro\u00df, Jochen K\u00f6nemann, and Laura Sanit\u00e0. 2018. Approximating weighted tree augmentation via Chv\u00e1tal-Gomory cuts. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 817\u2013831."},{"key":"e_1_3_2_1_19_1","volume-title":"A quick proof for the cactus representation of mincuts","author":"Fleiner Tam\u00e1s","unstructured":"Tam\u00e1s Fleiner and Andr\u00e1s Frank. 2009. A quick proof for the cactus representation of mincuts. Egerv\u00e1ry Research Group, Budapest. www.cs.elte.hu\/egres"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90059-7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102414910"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/080732572"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1541872.1541876"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585864"},{"key":"e_1_3_2_1_26_1","volume-title":"Minimum Bounded Degree Spanning Trees. In Symposium on Foundations of Computer Science (FOCS). 273\u2013282","author":"Goemans Michel X.","year":"2006","unstructured":"Michel X. Goemans. 2006. Minimum Bounded Degree Spanning Trees. In Symposium on Foundations of Computer Science (FOCS). 273\u2013282."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112670.3113039"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 1598\u20131611","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\u20131611."},{"key":"e_1_3_2_1_29_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC). 632\u2013645","author":"Grandoni F.","unstructured":"F. Grandoni, C. Kalaitzis, and R. Zenklusen. 2018. Improved approximation for tree augmentation: Saving by rewiring. In Annual ACM Symposium on Theory of Computing (STOC). 632\u2013645."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"Finding Almost Tight Witness Trees","volume":"79","author":"Hyatt-Denesik D.","year":"2023","unstructured":"D. Hyatt-Denesik, A. Jabal Ameli, and Sanit\u00e0 L.. 2023. Finding Almost Tight Witness Trees. In International Colloquium on Automata, Languages and Programming (ICALP). 79:1\u201379:16.","journal-title":"International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_32_1","unstructured":"Jennifer Iglesias and R Ravi. 2017. Coloring Down: 3\/2-approximation for special cases of the weighted tree augmentation problem. arXiv preprint arXiv:1707.05240."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0450"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00084"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520062"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0052"},{"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.1145\/335305.335371"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780600"},{"key":"e_1_3_2_1_43_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 International Colloquium on Automata, Languages and Programming (ICALP). 606\u2013616."},{"key":"e_1_3_2_1_44_1","volume-title":"Iterative Methods in Combinatorial Optimization","author":"Lau Lap-Chi","unstructured":"Lap-Chi Lau, R. Ravi, and Mohit Singh. 2011. Iterative Methods in Combinatorial Optimization (1st ed.). Cambridge University Press, New York, NY, USA.","edition":"1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2773-4"},{"key":"e_1_3_2_1_47_1","volume-title":"Annual European Symposium on Algorithms (ESA). 61:1\u201361:14","author":"Nutov Z.","year":"2017","unstructured":"Z. Nutov. 2017. On the tree augmentation problem. In Annual European Symposium on Algorithms (ESA). 61:1\u201361:14."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.07.006"},{"key":"e_1_3_2_1_49_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC). 140\u2013149","author":"Phillips Cynthia A","year":"1997","unstructured":"Cynthia A Phillips, Cliff Stein, Eric Torng, and Joel Wein. 1997. Optimal time-critical scheduling via resource augmentation. In Annual ACM Symposium on Theory of Computing (STOC). 140\u2013149."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"David Pritchard. 2011. k-Edge-Connectivity: Approximation and LP Relaxation. In Approximation and Online Algorithms.","DOI":"10.1007\/978-3-642-18318-8_20"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Ramamoorthi Ravi and Mohit Singh. 2006. Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs. In International Colloquium on Automata Languages and Programming (ICALP). 169\u2013180.","DOI":"10.1007\/11786986_16"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Tim Roughgarden. 2020. Resource Augmentation..","DOI":"10.1017\/9781108637435.006"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629366"},{"key":"e_1_3_2_1_55_1","volume-title":"Tarjan","author":"Sleator Daniel D.","year":"1985","unstructured":"Daniel D. Sleator and Robert E. Tarjan. 1985. Amortized Efficiency of List Update and Paging Rules. Commun. ACM, 28, 2 (1985), feb, 202\u2013208."},{"key":"e_1_3_2_1_56_1","unstructured":"Vera Traub and Rico Zenklusen. 2021. A Better-Than-2 Approximation for Weighted Tree Augmentation."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.128"},{"key":"e_1_3_2_1_58_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC).","author":"Traub V.","unstructured":"V. Traub and R. Zenklusen. 2023. A (1.5+\u03b5 )-Approximation Algorithm for Weighted Connectivity Augmentation. In Annual ACM Symposium on Theory of Computing (STOC)."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649715","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":58,"alternative-id":["10.1145\/3618260.3649715","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649715","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}