{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T06:04:19Z","timestamp":1759730659541,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"LabEx PERSYVAL-Lab","award":["ANR 11-LABX-0025"],"award-info":[{"award-number":["ANR 11-LABX-0025"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"crossref","award":["359525"],"award-info":[{"award-number":["359525"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>\n            We give a new, strongly polynomial-time algorithm and improved analysis for the metric\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            path Traveling Salesman Problem (TSP). It finds a tour of cost less than 1.53 times the optimum of the subtour elimination linear program (LP), while known examples show that 1.5 is a lower bound for the integrality gap.\n          <\/jats:p>\n          <jats:p>A key new idea is the deletion of some edges of the spanning trees used in the best-of-many Christofides-Serdyukov-algorithm, which is then accompanied by novel arguments of the analysis: edge-deletion disconnects the trees, and the arising forests are then partly reconnected by \u201cparity correction.\u201d We show that the arising \u201cconnectivity correction\u201d can be achieved for a minor extra cost.<\/jats:p>\n          <jats:p>On the one hand, this algorithm and analysis extend previous tools such as the best-of-many Christofides-Serdyukov-algorithm. On the other hand, powerful new tools are solicited, such as a flow problem for analyzing the reconnection cost, and the construction of a set of more and more restrictive spanning trees, each of which can still be found by the greedy algorithm. We show that these trees, which are easy to compute, can replace the spanning trees of the best-of-many Christofides-Serdyukov-algorithm.<\/jats:p>\n          <jats:p>These new methods lead to improving the integrality ratio and approximation guarantee below 1.53, as was shown in the preliminary, shortened version of this article that appeared in FOCS 2016. The algorithm and analysis have been significantly simplified in the current article, while details and explanations have been added.<\/jats:p>","DOI":"10.1145\/3326123","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T12:28:42Z","timestamp":1559824122000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["The Salesman\u2019s Improved Paths through Forests"],"prefix":"10.1145","volume":"66","author":[{"given":"Andr\u00e1s","family":"Seb\u0151","sequence":"first","affiliation":[{"name":"CNRS, Universit\u00e9 Grenoble Alpes, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anke Van","family":"Zuylen","sequence":"additional","affiliation":[{"name":"College of William 8 Mary, Williamsburg VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/2818310"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1515\/9781400841103"},{"unstructured":"William H. Cunningham. 1986. On Bounds for the Metric TSP. Unpublished manuscript.  William H. Cunningham. 1986. On Bounds for the Metric TSP. Unpublished manuscript.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1287\/opre.2.4.393"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/BF01580113"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/BF02579200"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1016\/j.orl.2013.08.006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/14096712X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/0205049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.5555\/3288898.3288943"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1007\/BF02579273"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/0167-6377(91)90016-I"},{"unstructured":"D. S. Johnson and C. H. Papadimitriou. 1985. Performance guarantees for heuristics. In The Traveling Salesman Problem. Wiley Chichester 145--180.  D. S. Johnson and C. H. Papadimitriou. 1985. Performance guarantees for heuristics. In The Traveling Salesman Problem. Wiley Chichester 145--180.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/2739008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1016\/j.orl.2017.11.002"},{"volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial Optimization\u2014Polyhedra and Efficiency . Springer . Alexander Schrijver. 2003. Combinatorial Optimization\u2014Polyhedra and Efficiency. Springer.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-3-642-36694-9_31"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1109\/FOCS.2016.21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_2_1_21_1","first-page":"76","article-title":"On some extremal walks in graphs","volume":"17","author":"Serdyukov A.","year":"1978","unstructured":"A. Serdyukov . 1978 . On some extremal walks in graphs . Upravlyaemye Sistemy 17 (1978), 76 -- 79 . A. Serdyukov. 1978. On some extremal walks in graphs. Upravlyaemye Sistemy 17 (1978), 76--79.","journal-title":"Upravlyaemye Sistemy"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0020-0190(90)90028-V"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/3174304.3175426"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1109\/FOCS.2018.00078"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/j.orl.2019.02.005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/15M1010531"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1007\/BFb0120913"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.5555\/3310435.3310528"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326123","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,5]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3326123"],"URL":"https:\/\/doi.org\/10.1145\/3326123","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,6,5]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}