{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T21:06:05Z","timestamp":1774127165780,"version":"3.50.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,7]],"date-time":"2019-03-07T00:00:00Z","timestamp":1551916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"\n We show that there is a polynomial-time algorithm with approximation guarantee 3\/2+\u03b5 for the\n s<\/jats:italic>\n -\n t<\/jats:italic>\n -path TSP, for any fixed \u03b5 > 0.\n <\/jats:p>\n \n It is well-known that Wolsey\u2019s analysis of Christofide algorithm also works for the\n s<\/jats:italic>\n -\n t<\/jats:italic>\n -path TSP with its natural LP relaxation, except for the\n narrow cuts<\/jats:italic>\n (in which the LP solution has a value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut\n lonely<\/jats:italic>\n ) or at least three (then call the cut\n busy<\/jats:italic>\n ). Our algorithm \u201cguesses\u201d (by dynamic programming) lonely cuts and edges. Then, we partition the instance into smaller instances and strengthen the LP, requiring a value of at least three for busy cuts. By setting up a\n k<\/jats:italic>\n -stage recursive dynamic program, we can compute a spanning tree (\n V<\/jats:italic>\n ,\n S<\/jats:italic>\n ) and an LP solution\n y<\/jats:italic>\n such that (\u00bd+\n O<\/jats:italic>\n (2\n \n \u2212\n k<\/jats:italic>\n <\/jats:sup>\n ))\n y<\/jats:italic>\n is in the\n T<\/jats:italic>\n -join polyhedron, where\n T<\/jats:italic>\n is the set of vertices whose degree in\n S<\/jats:italic>\n has the wrong parity.\n <\/jats:p>","DOI":"10.1145\/3309715","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T13:16:43Z","timestamp":1552051003000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Approaching 3\/2 for the\n s<\/i>\n -\n t<\/i>\n -path TSP"],"prefix":"10.1145","volume":"66","author":[{"given":"Vera","family":"Traub","sequence":"first","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818310"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112670.3113039"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3288898.3288943"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902503"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585735"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Seb\u0151 A.","year":"2016"},{"key":"e_1_2_1_12_1","first-page":"76","article-title":"Some extremal bypasses in graphs {in Russian}","volume":"17","author":"Serdjukov A. I.","year":"1978","journal-title":"Upravlyaemye Sistemy"},{"key":"e_1_2_1_13_1","unstructured":"V. Traub and J. Vygen. 2018. An improved upper bound on the integrality ratio for the s-t-path TSP. Operations Research Letters to appear. V. Traub and J. Vygen. 2018. An improved upper bound on the integrality ratio for the s - t -path TSP. Operations Research Letters to appear."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1010531"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120913"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310528"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309715","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:36Z","timestamp":1750204416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,7]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3309715"],"URL":"https:\/\/doi.org\/10.1145\/3309715","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,7]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}