{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:11:28Z","timestamp":1787389888804,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1813135, CCF-1552097, CCF-1907845"],"award-info":[{"award-number":["CCF-1813135, CCF-1552097, CCF-1907845"]}]},{"name":"ONR YIP grant","award":["N00014-17-1-2429"],"award-info":[{"award-number":["N00014-17-1-2429"]}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-20-1-0212"],"award-info":[{"award-number":["FA9550-20-1-0212"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451009","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"32-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":86,"title":["A (slightly) improved approximation algorithm for metric TSP"],"prefix":"10.1145","author":[{"given":"Anna R.","family":"Karlin","sequence":"first","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Klein","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shayan Oveis","family":"Gharan","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Shayan Oveis Gharan, and Cynthia Vinzant","author":"Anari Nima","year":"2018","unstructured":"Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. 2018. Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. In FOCS, Mikkel Thorup (Ed.). IEEE Computer Society, 35\u201346."},{"key":"e_1_3_2_1_2_1","volume-title":"Cook","author":"Applegate David L.","year":"2007","unstructured":"David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. 2007. The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton, NJ, USA."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora. 1996. Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In FOCS. 2\u201311.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"e_1_3_2_1_4_1","unstructured":"Sanjeev Arora Michelangelo Grigni David Karger Philip Klein and Andrzej Woloszyn. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In SODA. 33\u201341."},{"key":"e_1_3_2_1_5_1","volume-title":"Shayan Oveis Gharan, and Amin Saberi","author":"Asadpour Arash","year":"2010","unstructured":"Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi. 2010. An O(log n\/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. In SODA. 379\u2013389."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s A. Bencz\\'ur. 1995. A Representation of Cuts within 6\/5 Times the Edge Connectivity with Applications. In FOCS. 92\u2013102.","DOI":"10.1109\/SFCS.1995.492466"},{"key":"e_1_3_2_1_8_1","first-page":"103","article-title":"Deformable Polygon Representation and Near-Mincuts. Building Bridges: Between Mathematics and Computer Science, M. Groetschel and G.O.H. Katona, Eds","volume":"19","author":"Goemans Andr\u00e1s A.","year":"2008","unstructured":"Andr\u00e1s A. Bencz\\'ur and Michel X. Goemans. 2008. Deformable Polygon Representation and Near-Mincuts. Building Bridges: Between Mathematics and Computer Science, M. Groetschel and G.O.H. Katona, Eds., Bolyai Society Mathematical Studies 19 (2008), 103\u2013135.","journal-title":"Bolyai Society Mathematical Studies"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00618-8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2011.05.002"},{"key":"e_1_3_2_1_11_1","first-page":"33","article-title":"Structure of the extreme points of the subtour elimination polytope of the STSP","volume":"23","author":"Boyd S.","year":"2010","unstructured":"S. Boyd and P. Elliott-Magwood. 2010. Structure of the extreme points of the subtour elimination polytope of the STSP. In Combinatorial Optimization and Discrete Algorithms, Vol. B23. 33\u201347.","journal-title":"Combinatorial Optimization and Discrete Algorithms"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588786"},{"key":"e_1_3_2_1_13_1","volume-title":"Carr and Santosh Vempala","author":"Robert","year":"2000","unstructured":"Robert D. Carr and Santosh Vempala. 2000. Towards a 4\/3 approximation for the asymmetric traveling salesman problem. In SODA. 116\u2013125."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.7.1.58"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703287"},{"key":"e_1_3_2_1_17_1","unstructured":"Erik D. Demaine MohammadTaghi Hajiaghayi and Bojan Mohar. 2007. Approximation algorithms via contraction decomposition. In SODA. 278\u2013287."},{"key":"e_1_3_2_1_18_1","unstructured":"E.A. Dinits A.V. Karzanov and M.V. Lomonosov. 1976. On the structure of a family of minimal weighted cuts in graphs. Studies in Discrete Mathematics (in Russian) ed. A.A. Fridman 290-306 Nauka (Moskva) (1976)."},{"key":"e_1_3_2_1_19_1","volume-title":"Combinatorial Structures and Their Applications. Gordon and Breach","author":"Edmonds Jack","unstructured":"Jack Edmonds. 1970. Submodular functions, matroids and certain polyhedra. In Combinatorial Structures and Their Applications. Gordon and Breach, New York, NY, USA, 69\u201387."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.09.005"},{"key":"e_1_3_2_1_23_1","first-page":"1109","article-title":"An Experimental Evaluation of the Best-of-Many Christofides","volume":"78","author":"Genova Kyle","year":"2017","unstructured":"Kyle Genova and David P. Williamson. 2017. An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem. Algorithmica 78, 4 (2017), 1109\u20131130.","journal-title":"Algorithm for the Traveling Salesman Problem. Algorithmica"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585563"},{"key":"e_1_3_2_1_25_1","volume-title":"FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Grigni M.","unstructured":"M. Grigni, E. Koutsoupias, and C. Papadimitriou. 1995. An approximation scheme for planar graph TSP. In FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Washington, DC, USA, 640. isbn:0-8186-7183-1"},{"key":"e_1_3_2_1_26_1","volume-title":"Hyperbolic polynomials approach to Van der Waerden\/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications","author":"Gurvits Leonid","unstructured":"Leonid Gurvits. 2006. Hyperbolic polynomials approach to Van der Waerden\/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In STOC, Jon M. Kleinberg (Ed.). ACM, 417\u2013426."},{"key":"e_1_3_2_1_27_1","article-title":"Van der Waerden\/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all","volume":"15","author":"Gurvits Leonid","year":"2008","unstructured":"Leonid Gurvits. 2008. Van der Waerden\/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all. Electr. J. Comb. 15, 1 (2008). http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r66.html","journal-title":"Electr. J. Comb."},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Towards Improving Christofides Algorithm for Half-Integer TSP. In ESA (LIPIcs, Vol. 144), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.)","volume":"56","author":"Haddadan Arash","year":"2019","unstructured":"Arash Haddadan and Alantha Newman. 2019. Towards Improving Christofides Algorithm for Half-Integer TSP. In ESA (LIPIcs, Vol. 144), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 56:1\u201356:12.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_29_1","unstructured":"Arash Haddadan Alantha Newman and R. Ravi. 2017. Cover and Conquer: Augmenting Decompositions for Connectivity Problems. (2017). http:\/\/arxiv.org\/abs\/1707.05387 abs\/1707.05387."},{"key":"e_1_3_2_1_30_1","unstructured":"G. H. Hardy J. E. Littlewood and G. Polya. 1952. Inequalities. Cambridge Univ. Press."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728178"},{"key":"e_1_3_2_1_33_1","volume-title":"An improved approximation algorithm for TSP in the half integral case","author":"Karlin Anna R.","unstructured":"Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. 2020. An improved approximation algorithm for TSP in the half integral case. In STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, 28\u201339."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.06.003"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Philip N. Klein. 2005. A linear-time approximation scheme for planar weighted TSP. In FOCS. 647\u2013657.","DOI":"10.1109\/SFCS.2005.7"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Tobias Moemke and Ola Svensson. 2011. Approximating Graphic TSP by Matchings. In FOCS. 560\u2013569.","DOI":"10.1109\/FOCS.2011.56"},{"key":"e_1_3_2_1_38_1","unstructured":"M Mucha. 2012. $\\frac139$-approximation for graphic TSP.. In STACS. 30\u201341."},{"key":"e_1_3_2_1_39_1","volume-title":"A Randomized Rounding Approach to the Traveling Salesman Problem","author":"Gharan Shayan Oveis","unstructured":"Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2011. A Randomized Rounding Approach to the Traveling Salesman Problem. In FOCS. IEEE Computer Society, 550\u2013559. isbn:978-0-7695-4571-4"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Frans Schalekamp David P. Williamson and Anke van Zuylen. 2012. A proof of the Boyd-Carr conjecture. In SODA. 1477\u20131486.","DOI":"10.1137\/1.9781611973099.117"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0608"},{"key":"e_1_3_2_1_42_1","unstructured":"Andr\u00e1s Seb\u00f6 and Jens Vygen. 2012. Shorter Tours by Nicer Ears:. (2012). CoRR abs\/1201.1870."},{"key":"e_1_3_2_1_43_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. http:\/\/nas1.math.nsc.ru\/aim\/journals\/us\/us17\/us17_007.pdf"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90028-V"},{"key":"e_1_3_2_1_45_1","volume-title":"Vishnoi","author":"Straszak Damian","year":"2019","unstructured":"Damian Straszak and Nisheeth K. Vishnoi. 2019. Maximum Entropy Distributions: Bit Complexity and Stability. In COLT (Proceedings of Machine Learning Research, Vol. 99), Alina Beygelzimer and Daniel Hsu (Eds.). PMLR, 2861\u20132891."},{"key":"e_1_3_2_1_46_1","volume-title":"Reducing path TSP to TSP","author":"Traub Vera","unstructured":"Vera Traub, Jens Vygen, and Rico Zenklusen. 2020. Reducing path TSP to TSP. In STOC, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, 14\u201327."},{"key":"e_1_3_2_1_47_1","volume-title":"Slugina","author":"van Bevern Ren\u00e9","year":"2020","unstructured":"Ren\u00e9 van Bevern and Viktoriia A. Slugina. 2020. A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem. (2020). https:\/\/arxiv.org\/abs\/2004.02437"},{"key":"e_1_3_2_1_48_1","volume-title":"Combinatorial Optimization II. Mathematical Programming Studies","author":"Wolsey Laurence A.","unstructured":"Laurence A. Wolsey. 1980. Heuristic analysis, linear programming and branch and bound. In Combinatorial Optimization II. Mathematical Programming Studies, Vol. 13. Springer Berlin Heidelberg, 121\u2013134."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451009","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":46,"alternative-id":["10.1145\/3406325.3451009","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451009","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}