{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T21:12:32Z","timestamp":1773781952898,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":25,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384256","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"14-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Reducing path TSP to TSP"],"prefix":"10.1145","author":[{"given":"Vera","family":"Traub","sequence":"first","affiliation":[{"name":"University of Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[{"name":"University of Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818310"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645464"},{"key":"e_1_3_2_1_3_1","first-page":"126","volume":"72","author":"Cheriyan J.","year":"2015","unstructured":"J. Cheriyan , Z. Friggstad , and Z. Gao . Approximating minimum-cost connected T-joins. Algorithmica , 72 : 126 - 147 , 2015 . Short version appeared in APPROX\/RANDOM 2012. J. Cheriyan, Z. Friggstad, and Z. Gao. Approximating minimum-cost connected T-joins. Algorithmica, 72 : 126-147, 2015. Short version appeared in APPROX\/RANDOM 2012.","journal-title":"Approximating minimum-cost connected T-joins. Algorithmica"},{"key":"e_1_3_2_1_5_1","first-page":"104","volume-title":"Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Feige U.","year":"2007","unstructured":"U. Feige and M. Singh . Improved approximation algorithms for traveling salesperson tours and paths in directed graphs . In Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) , pages 104 - 118 , 2007 . U. Feige and M. Singh. Improved approximation algorithms for traveling salesperson tours and paths in directed graphs. In Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 104-118, 2007."},{"key":"e_1_3_2_1_6_1","volume-title":"An LP-based 32-approximation algorithm for the s-t path graph traveling salesman problem. Operations Research Letters, 41 : 615-617","author":"Gao Z.","year":"2013","unstructured":"Z. Gao . An LP-based 32-approximation algorithm for the s-t path graph traveling salesman problem. Operations Research Letters, 41 : 615-617 , 2013 . Z. Gao. An LP-based 32-approximation algorithm for the s-t path graph traveling salesman problem. Operations Research Letters, 41 : 615-617, 2013."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3288898.3288943"},{"key":"e_1_3_2_1_8_1","volume-title":"Analysis of Christofides' heuristic: Some paths are more dificult than cycles. Operations Research Letters, 10 ( 5 ): 291-295","author":"Hoogeveen J.A.","year":"1991","unstructured":"J.A. Hoogeveen . Analysis of Christofides' heuristic: Some paths are more dificult than cycles. Operations Research Letters, 10 ( 5 ): 291-295 , 1991 . J.A. Hoogeveen. Analysis of Christofides' heuristic: Some paths are more dificult than cycles. Operations Research Letters, 10 ( 5 ): 291-295, 1991."},{"key":"e_1_3_2_1_9_1","volume-title":"A factor 2 approximation algorithm for the generalized Steiner Network Problem. Combinatorica, 21 : 39-60","author":"Jain K.","year":"2001","unstructured":"K. Jain . A factor 2 approximation algorithm for the generalized Steiner Network Problem. Combinatorica, 21 : 39-60 , 2001 . Short version appeared in FOCS 1998. K. Jain. A factor 2 approximation algorithm for the generalized Steiner Network Problem. Combinatorica, 21 : 39-60, 2001. Short version appeared in FOCS 1998."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.06.003"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739008"},{"key":"e_1_3_2_1_12_1","volume-title":"Theory of Computing Systems, 55 ( 4 ): 640-657","author":"Mucha M.","year":"2014","unstructured":"M. Mucha . 193-approximation for graphic TSP. Theory of Computing Systems, 55 ( 4 ): 640-657 , 2014 . Short version appeared in STACS 2012. M. Mucha. 193-approximation for graphic TSP. Theory of Computing Systems, 55 ( 4 ): 640-657, 2014. Short version appeared in STACS 2012."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.94"},{"key":"e_1_3_2_1_14_1","first-page":"550","volume-title":"Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Oveis Gharan S.","year":"2011","unstructured":"S. Oveis Gharan , A. Saberi , and M. Singh . A randomized rounding approach to the Traveling Salesman Problem . In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 550 - 559 , 2011 . S. Oveis Gharan, A. Saberi, and M. Singh. A randomized rounding approach to the Traveling Salesman Problem. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 550-559, 2011."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781820.2781821"},{"key":"e_1_3_2_1_16_1","series-title":"SIAM Journal on Computing, 26 ( 2 ): 582-603","volume-title":"Potentials in undirected graphs and planar multiflows","author":"Seb\u0151 A.","year":"1997","unstructured":"A. Seb\u0151 . Potentials in undirected graphs and planar multiflows . SIAM Journal on Computing, 26 ( 2 ): 582-603 , 1997 . A. Seb\u0151. Potentials in undirected graphs and planar multiflows. SIAM Journal on Computing, 26 ( 2 ): 582-603, 1997."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"e_1_3_2_1_18_1","volume-title":"The salesman's improved paths through forests. Journal of the ACM, 66 ( 4 ): 28 : 1-28 : 16","author":"Seb\u0151 A.","year":"2019","unstructured":"A. Seb\u0151 and A. van Zuylen . The salesman's improved paths through forests. Journal of the ACM, 66 ( 4 ): 28 : 1-28 : 16 , 2019 . Short version appeared in FOCS 2016. A. Seb\u0151 and A. van Zuylen. The salesman's improved paths through forests. Journal of the ACM, 66 ( 4 ): 28 : 1-28 : 16, 2019. Short version appeared in FOCS 2016."},{"key":"e_1_3_2_1_19_1","volume-title":"Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 34 ( 5 ): 597-629","author":"Seb\u0151 A.","year":"2014","unstructured":"A. Seb\u0151 and J. Vygen . Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 34 ( 5 ): 597-629 , 2014 . A. Seb\u0151 and J. Vygen. Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 34 ( 5 ): 597-629, 2014."},{"key":"e_1_3_2_1_20_1","volume-title":"Some extremal bypasses in graphs [in Russian]. Upravlyaemye Sistemy, 17 : 76-79","author":"Serdjukov A. I.","year":"1978","unstructured":"A. I. Serdjukov . Some extremal bypasses in graphs [in Russian]. Upravlyaemye Sistemy, 17 : 76-79 , 1978 . A. I. Serdjukov. Some extremal bypasses in graphs [in Russian]. Upravlyaemye Sistemy, 17 : 76-79, 1978."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00078"},{"key":"e_1_3_2_1_22_1","volume-title":"Approaching 32 for the s-t path TSP. Journal of the ACM, 66 ( 2 ): 14 : 1-14 : 17","author":"Traub V.","year":"2019","unstructured":"V. Traub and J. Vygen . Approaching 32 for the s-t path TSP. Journal of the ACM, 66 ( 2 ): 14 : 1-14 : 17 , 2019 . Short version appeared in SODA 2018. V. Traub and J. Vygen. Approaching 32 for the s-t path TSP. Journal of the ACM, 66 ( 2 ): 14 : 1-14 : 17, 2019. Short version appeared in SODA 2018."},{"key":"e_1_3_2_1_23_1","volume-title":"Reducing Path TSP to TSP","author":"Traub V.","year":"2019","unstructured":"V. Traub , J. Vygen , and R. Zenklusen . Reducing Path TSP to TSP , 2019 . https: \/\/arxiv.org\/abs\/ 1907.10376. V. Traub, J. Vygen, and R. Zenklusen. Reducing Path TSP to TSP, 2019. https: \/\/arxiv.org\/abs\/ 1907.10376."},{"key":"e_1_3_2_1_24_1","series-title":"SIAM Journal on Discrete Mathematics, 30 ( 2 ): 875-894","volume-title":"Reassembling trees for the traveling salesman","author":"Vygen J.","year":"2016","unstructured":"J. Vygen . Reassembling trees for the traveling salesman . SIAM Journal on Discrete Mathematics, 30 ( 2 ): 875-894 , 2016 . J. Vygen. Reassembling trees for the traveling salesman. SIAM Journal on Discrete Mathematics, 30 ( 2 ): 875-894, 2016."},{"key":"e_1_3_2_1_25_1","volume-title":"INFORMS Journal on Computing, 27 ( 4 ): 636-645","author":"Xu Z.","year":"2015","unstructured":"Z. Xu and B Rodrigues . A 3\/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS Journal on Computing, 27 ( 4 ): 636-645 , 2015 . Z. Xu and B Rodrigues. A 3\/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS Journal on Computing, 27 ( 4 ): 636-645, 2015."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.93"}],"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.3384256","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384256","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.3384256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":25,"alternative-id":["10.1145\/3357713.3384256","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384256","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"}}]}}