{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T02:34:41Z","timestamp":1786588481486,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR-YIP","award":["N00014-17-1-2429"],"award-info":[{"award-number":["N00014-17-1-2429"]}]},{"name":"NSF","award":["CCF-1813135, CCF-1552097, CCF- 1907845"],"award-info":[{"award-number":["CCF-1813135, CCF-1552097, CCF- 1907845"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384273","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"28-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["An improved approximation algorithm for TSP in the half integral case"],"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":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"33","volume-title":"SODA","author":"Arora Sanjeev","year":"1998","unstructured":"[AGK+98] Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , and Andrzej Woloszyn . A polynomial-time approximation scheme for weighted planar graph tsp . In SODA , pages 33 - 41 , 1998 . [AGK+98] Sanjeev Arora, Michelangelo Grigni, David Karger, Philip Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph tsp. In SODA, pages 33-41, 1998."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2017.1603"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875526"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00618-8"},{"key":"e_1_3_2_1_5_1","volume-title":"Finding low cost tsp and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization, 8 ( 4 ): 525-539","author":"Boyd Sylvia","year":"2011","unstructured":"[BC11] Sylvia Boyd and Robert Carr . Finding low cost tsp and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization, 8 ( 4 ): 525-539 , 2011 . [BC11] Sylvia Boyd and Robert Carr. Finding low cost tsp and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization, 8 ( 4 ): 525-539, 2011."},{"key":"e_1_3_2_1_6_1","first-page":"33","volume-title":"Combinatorial Optimization and Discrete Algorithms","author":"Boyd S.","year":"2010","unstructured":"[BEM10] S. Boyd and P. Elliott-Magwood . Structure of the extreme points of the subtour elimination polytope of the stsp . In Combinatorial Optimization and Discrete Algorithms , volume B 23 , pages 33 - 47 , Research Institute for Mathematical Sciences , Kyoto University , Kyoto Japan, 2010 . [BEM10] S. Boyd and P. Elliott-Magwood. Structure of the extreme points of the subtour elimination polytope of the stsp. In Combinatorial Optimization and Discrete Algorithms, volume B23, pages 33-47, Research Institute for Mathematical Sciences, Kyoto University, Kyoto Japan, 2010."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588786"},{"key":"e_1_3_2_1_8_1","first-page":"111","volume-title":"IPCO","author":"Sylvia","year":"2017","unstructured":"[BS17] Sylvia C. Boyd and Andr\u00e1s Seb\u00f6. The saleman's improved tours for fundamental classes . In IPCO , pages 111 - 122 , 2017 . [BS17] Sylvia C. Boyd and Andr\u00e1s Seb\u00f6. The saleman's improved tours for fundamental classes. In IPCO, pages 111-122, 2017."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69346-7_9"},{"key":"e_1_3_2_1_11_1","first-page":"116","volume-title":"SODA","author":"Robert","year":"2000","unstructured":"[CV00] Robert D. Carr and Santosh Vempala. Towards a 4\/3 approximation for the asymmetric traveling salesman problem . In SODA , pages 116 - 125 , 2000 . [CV00] Robert D. Carr and Santosh Vempala. Towards a 4\/3 approximation for the asymmetric traveling salesman problem. In SODA, pages 116-125, 2000."},{"key":"e_1_3_2_1_12_1","first-page":"393","volume":"2","author":"Dantzig G","unstructured":"[DFJ54] G Dantzig , R Fulkerson , and S Johnson . Solution of a large-scale travelingsalesman problem. Operations Research , 2 : 393 - 410 , 1954. [DFJ54] G Dantzig, R Fulkerson, and S Johnson. Solution of a large-scale travelingsalesman problem. Operations Research, 2 : 393-410, 1954.","journal-title":"Operations Research"},{"key":"e_1_3_2_1_13_1","first-page":"278","volume-title":"SODA","author":"Demaine Erik D.","year":"2007","unstructured":"[DHM07] Erik D. Demaine , MohammadTaghi Hajiaghayi , and Bojan Mohar . Approximation algorithms via contraction decomposition . In SODA , pages 278 - 287 , 2007 . [DHM07] Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. Approximation algorithms via contraction decomposition. In SODA, pages 278-287, 2007."},{"key":"e_1_3_2_1_14_1","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds Jack","year":"1970","unstructured":"[Edm70] Jack Edmonds . Submodular functions, matroids and certain polyhedra . In Combinatorial Structures and Their Applications , pages 69 - 87 , New York, NY, USA , 1970 . Gordon and Breach. [Edm70] Jack Edmonds. Submodular functions, matroids and certain polyhedra. In Combinatorial Structures and Their Applications, pages 69-87, New York, NY, USA, 1970. Gordon and Breach."},{"key":"e_1_3_2_1_15_1","volume-title":"Matching, euler tours and the chinese postman. Mathematical Programming, 5 ( 1 ): 88-124","author":"Edmonds Jack","year":"1973","unstructured":"[EJ73] Jack Edmonds and Ellis L. Johnson . Matching, euler tours and the chinese postman. Mathematical Programming, 5 ( 1 ): 88-124 , 1973 . [EJ73] Jack Edmonds and Ellis L. Johnson. Matching, euler tours and the chinese postman. Mathematical Programming, 5 ( 1 ): 88-124, 1973."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492665"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.09.005"},{"key":"e_1_3_2_1_20_1","first-page":"335","volume":"69","author":"Goemans Michel X.","unstructured":"[Goe95] Michel X. Goemans . Worst-case comparison of valid inequalities for the tsp. MATH. PROG , 69 : 335 - 349 , 1995. [Goe95] Michel X. Goemans. Worst-case comparison of valid inequalities for the tsp. MATH. PROG, 69 : 335-349, 1995.","journal-title":"PROG"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_22_1","volume-title":"Towards improving christofides algorithm for half-integer TSP. abs\/","author":"Haddadan Arash","year":"1907","unstructured":"[HN19] Arash Haddadan and Alantha Newman . Towards improving christofides algorithm for half-integer TSP. abs\/ 1907 .02120, 2019. [HN19] Arash Haddadan and Alantha Newman. Towards improving christofides algorithm for half-integer TSP. abs\/ 1907.02120, 2019."},{"key":"e_1_3_2_1_23_1","volume-title":"Cover and conquer: Augmenting decompositions for connectivity problems. CoRR, abs\/1707.05387","author":"Haddadan Arash","year":"2017","unstructured":"[HNR17] Arash Haddadan , Alantha Newman , and R. Ravi . Cover and conquer: Augmenting decompositions for connectivity problems. CoRR, abs\/1707.05387 , 2017 . [HNR17] Arash Haddadan, Alantha Newman, and R. Ravi. Cover and conquer: Augmenting decompositions for connectivity problems. CoRR, abs\/1707.05387, 2017."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728178"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.7"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_53"},{"key":"e_1_3_2_1_27_1","first-page":"1298","volume":"28","author":"Mitchell Joseph SB","unstructured":"[Mit99] Joseph SB Mitchell . Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM Journal on Computing , 28 ( 4 ): 1298 - 1309 , 1999. [Mit99] Joseph SB Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM Journal on Computing, 28 ( 4 ): 1298-1309, 1999.","journal-title":"Computing"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.56"},{"key":"e_1_3_2_1_29_1","first-page":"30","volume-title":"STACS","author":"Mucha M","year":"2012","unstructured":"[Muc12] M Mucha . 193-approximation for graphic tsp . In STACS , pages 30 - 41 , 2012 . [Muc12] M Mucha. 193-approximation for graphic tsp. In STACS, pages 30-41, 2012."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2747"},{"key":"e_1_3_2_1_32_1","volume-title":"Shorter tours by nicer ears:. CoRR abs\/1201","author":"Seb\u00f6 Andr\u00e1s","year":"1870","unstructured":"[SV12] Andr\u00e1s Seb\u00f6 and Jens Vygen . Shorter tours by nicer ears:. CoRR abs\/1201 . 1870 , 2012. [SV12] Andr\u00e1s Seb\u00f6 and Jens Vygen. Shorter tours by nicer ears:. CoRR abs\/1201. 1870, 2012."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90028-V"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.117"},{"key":"e_1_3_2_1_35_1","first-page":"403","volume":"39","author":"Schalekamp Frans","unstructured":"[SWvZ13] Frans Schalekamp , David P. Williamson , and Anke van Zuylen . 2-matchings, the traveling salesman problem, and the subtour lp: A proof of the boyd-carr conjecture. Mathematics of Operations Research , 39 ( 2 ): 403 - 417 , 2013. [SWvZ13] Frans Schalekamp, David P. Williamson, and Anke van Zuylen. 2-matchings, the traveling salesman problem, and the subtour lp: A proof of the boyd-carr conjecture. Mathematics of Operations Research, 39 ( 2 ): 403-417, 2013.","journal-title":"Operations Research"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120913"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384273","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384273","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":34,"alternative-id":["10.1145\/3357713.3384273","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384273","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}