{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:29:39Z","timestamp":1766068179008,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","funder":[{"name":"European Research Council","award":["805241-QIP, 759557-ALGOCom, CODY 101039914"],"award-info":[{"award-number":["805241-QIP, 759557-ALGOCom, CODY 101039914"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718288","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"166-177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the Held\u2013Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4450-8506","authenticated-orcid":false,"given":"Zhuan Khye","family":"Koh","sequence":"first","affiliation":[{"name":"Boston University, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9357-2299","authenticated-orcid":false,"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7169-0163","authenticated-orcid":false,"given":"Sorrachai","family":"Yingchareonthawornchai","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"},{"name":"ETH Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"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":"1439","article-title":"Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel","author":"Allen-Zhu Zeyuan","year":"2015","unstructured":"Zeyuan Allen-Zhu and Lorenzo Orecchia. 2015. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In SODA. 1439-1456.","journal-title":"SODA."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746573"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0440-4"},{"key":"e_1_3_2_1_5_1","volume-title":"Cook","author":"Applegate David L.","year":"2006","unstructured":"David L. Applegate, Robert E. Bixby, Va\u0161ek Chvat\u00e1l, and William J. Cook. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_8_1","first-page":"691","article-title":"Stateless distributed gradient descent for positive linear programs","author":"Awerbuch Baruch","year":"2008","unstructured":"Baruch Awerbuch and Rohit Khandekar. 2008. Stateless distributed gradient descent for positive linear programs. In STOC., 691-700.","journal-title":"STOC."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646119"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700379383"},{"key":"e_1_3_2_1_11_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. 90\u2013101.","DOI":"10.1007\/978-3-540-73420-8_10"},{"key":"e_1_3_2_1_12_1","first-page":"1","article-title":"A Simple Algorithm for Minimum Cuts in Near-Linear Time. In SWAT (LIPIcs, Vol. 162)","volume":"12","author":"Bhardwaj Nalin","year":"2020","unstructured":"Nalin Bhardwaj, Antonio Molina Lovett, and Bryce Sandlund. 2020. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In SWAT (LIPIcs, Vol. 162). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 12:1\u201312:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9662-2"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338241"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00106-7"},{"key":"e_1_3_2_1_17_1","first-page":"1","article-title":"Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. Approximation, Randomization, and Combinatorial Optimization","volume":"116","author":"Chalermsook Parinya","year":"2018","unstructured":"Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. 2018. Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. In Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, 8:1-8:19.","journal-title":"Algorithms and Techniques. In Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"e_1_3_2_1_18_1","volume-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022","volume":"20","author":"Chalermsook Parinya","year":"2022","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. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 37:1\u201337:20."},{"key":"e_1_3_2_1_19_1","volume-title":"Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 789\u2013800","author":"Chekuri Chandra","year":"2017","unstructured":"Chandra Chekuri and Kent Quanrud. 2017. Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 789\u2013800."},{"key":"e_1_3_2_1_20_1","volume-title":"Fast Approximations for Metric-TSP via Linear Programming. CoRR, abs\/1802.01242","author":"Chekuri Chandra","year":"2018","unstructured":"Chandra Chekuri and Kent Quanrud. 2018. Fast Approximations for Metric-TSP via Linear Programming. CoRR, abs\/1802.01242 (2018), arXiv:1802.01242. arxiv:1802.01242"},{"volume-title":"Worst-case analysis of a new heuristic for the traveling salesman","author":"Christofides Nicos","key":"e_1_3_2_1_21_1","unstructured":"Nicos Christofides. 1976. Worst-case analysis of a new heuristic for the traveling salesman. Carnegie Mellon University."},{"key":"e_1_3_2_1_22_1","volume-title":"Traveling Salesman: Mathematics at the Limits of Computation","author":"Cook William J.","year":"2012","unstructured":"William J. Cook. 2012. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545390"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982863"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314573"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Artur Czumaj and Andrzej Lingas. 2000. Fast approximation schemes for Euclidean multi-connectivity problems. In International Colloquium on Automata Languages and Programming. 856\u2013868.","DOI":"10.1007\/3-540-45022-X_72"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2.4.393"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0931"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175323"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90059-7"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"e_1_3_2_1_34_1","first-page":"345","article-title":"Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks","volume":"53","author":"Gabow Harold N","year":"2009","unstructured":"Harold N Gabow, Michel X Goemans, \u00c9va Tardos, and David P Williamson. 2009. Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks: An International Journal, 53, 4 (2009), 345\u2013357.","journal-title":"An International Journal"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.8"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210393"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585563"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112670.3113039"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188898"},{"key":"e_1_3_2_1_41_1","volume-title":"51st International Colloquium on Automata, Languages, and Programming, ICALP 2024","volume":"20","author":"Gurvits Leonid","year":"2024","unstructured":"Leonid Gurvits, Nathan Klein, and Jonathan Leake. 2024. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (LIPIcs, Vol. 297). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 79:1\u201379:20."},{"key":"e_1_3_2_1_42_1","volume-title":"Punnen","author":"Gutin Gregory","year":"2007","unstructured":"Gregory Gutin and Abraham P. Punnen. 2007. The Traveling Salesman Problem and Its Variations (Combinatorial Optimization, Vol. 12). Springer Science+Business Media."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.111"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00079-8"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649715"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520062"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00084"},{"volume-title":"Lagrangian relaxation based algorithms for convex programming problems. Ph. D. Dissertation","author":"Khandekar Rohit","key":"e_1_3_2_1_51_1","unstructured":"Rohit Khandekar. 2004. Lagrangian relaxation based algorithms for convex programming problems. Ph. D. Dissertation. Indian Institute of Technology Delhi."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"e_1_3_2_1_53_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. 606\u2013616."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a009"},{"key":"e_1_3_2_1_55_1","volume-title":"A. H. G. Rinnooy Kan, and D. B. Shmoys.","author":"Lawler E. L.","year":"1991","unstructured":"E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. 1991. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons."},{"key":"e_1_3_2_1_56_1","volume-title":"33rd ACM Symposium on Parallelism in Algorithms and Architectures","author":"L\u00f3pez-Mart\u00ednez Andr\u00e9s","year":"2021","unstructured":"Andr\u00e9s L\u00f3pez-Mart\u00ednez, Sagnik Mukhopadhyay, and Danupon Nanongkai. 2021. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. In SPAA \u201921: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021. ACM, 351\u2013361."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167211"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.52"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585735"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00246-8"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_3_2_1_66_1","volume-title":"WAOA (Lecture Notes in Computer Science","volume":"236","author":"Pritchard David","year":"2010","unstructured":"David Pritchard. 2010. k-Edge-Connectivity: Approximation and LP Relaxation. In WAOA (Lecture Notes in Computer Science, Vol. 6534). Springer, 225\u2013236."},{"key":"e_1_3_2_1_67_1","volume-title":"O nekotorykh ekstremal\u2019nykh obkhodakh v grafakh. Upravlyaemye sistemy, 17","author":"Serdyukov A. I.","year":"1978","unstructured":"A. I. Serdyukov. 1978. O nekotorykh ekstremal\u2019nykh obkhodakh v grafakh. Upravlyaemye sistemy, 17 (1978), 76\u201379."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90028-V"},{"volume-title":"Heuristic analysis, linear programming and branch and bound","author":"Wolsey Laurence A.","key":"e_1_3_2_1_70_1","unstructured":"Laurence A. Wolsey. 1980. Heuristic analysis, linear programming and branch and bound. Springer Berlin Heidelberg, 121\u2013134."},{"key":"e_1_3_2_1_71_1","volume-title":"Sequential and Parallel Algorithms for Mixed Packing and Covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001","author":"Young Neal E.","year":"2001","unstructured":"Neal E. Young. 2001. Sequential and Parallel Algorithms for Mixed Packing and Covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 538\u2013546."},{"key":"e_1_3_2_1_72_1","volume-title":"Nearly Linear-Time Approximation Schemes for Mixed Packing\/Covering and Facility-Location Linear Programs. CoRR, abs\/1407.3015","author":"Young Neal E.","year":"2014","unstructured":"Neal E. Young. 2014. Nearly Linear-Time Approximation Schemes for Mixed Packing\/Covering and Facility-Location Linear Programs. CoRR, abs\/1407.3015 (2014), arXiv:1407.3015. arxiv:1407.3015"}],"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.3718288","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:48:33Z","timestamp":1750693713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":72,"alternative-id":["10.1145\/3717823.3718288","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718288","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"}}]}}