{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:20:44Z","timestamp":1787322044156,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We study the metric $s$--$t$ path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875--886] improved on the long-standing $\\frac{5}{3}$-approximation factor and presented an algorithm that achieves an approximation factor of $\\frac{1+\\sqrt{5}}{2}\\approx1.61803$. Later, Seb\u00f6 [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362--374] further improved the approximation factor to $\\frac{8}{5}$. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the $s$--$t$ path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of $\\frac{3}{2}$ of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost $c$ can be rounded to an integral solution of cost at most $\\frac{3}{2}c$. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of $\\frac{3}{2}$.<\/jats:p>","DOI":"10.1137\/14096712x","type":"journal-article","created":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T16:01:39Z","timestamp":1437062499000},"page":"1133-1149","source":"Crossref","is-referenced-by-count":9,"title":["On the Metric $s$--$t$ Path Traveling Salesman Problem"],"prefix":"10.1137","volume":"29","author":[{"given":"Zhihan","family":"Gao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"H-C. An, R. Kleinberg, and D. B. Shmoys,\n                      Improving Christofides' algorithm for the $s$-$t$ path TSP\n                      , in Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886.","DOI":"10.1145\/2213977.2214055"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0337"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00032-1"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"J. Cheriyan, Z. Friggstad, and Z. Gao,\n                      Approximating minimum-cost connected T-joins\n                      , in Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2012, pp. 110-121.","DOI":"10.1007\/978-3-642-32512-0_10"},{"key":"atypb5","unstructured":"N. Christofides,\n                      Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem\n                      , Technical report, Graduate School of Industrial Administration, CMU, Pittsburgh, PA, 1976."},{"key":"atypb6","first-page":"27","author":"Edmonds J.","year":"2001","journal-title":"Germany"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90589-8"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Z. Gao,\n                      An LP-based 3\/2-approximation algorithm for the $s$-$t$ path graph traveling salesman problem\n                      , Operations Research Letters, 41 (2013), pp. 615-617.","DOI":"10.1016\/j.orl.2013.08.006"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"atypb10","unstructured":"L. Lova\u0301sz,\n                      Lecture\n                      , Conference of Graph Theory Prague, Czech Republic, 1974."},{"key":"atypb11","unstructured":"L. Lova\u0301sz,\n                      Combinatorial Problems and Exercises\n                      , North-Holland, Amsterdam, The Netherlands, 1979."},{"key":"atypb12","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics\n                      , Algorithms and Combinations 24, Springer, Berlin, Germany, 2003."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Sebo\u0308,\n                      Eight-fifth approximation for the path TSP\n                      , in Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374.","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"atypb15","first-page":"1","volume":"90","author":"Vygen J.","year":"2012","journal-title":"Mathematical Optimization Society Newsletter"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14096712X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:26Z","timestamp":1787318246000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14096712X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14096712X"],"URL":"https:\/\/doi.org\/10.1137\/14096712x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}