{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T05:14:38Z","timestamp":1779081278723,"version":"3.51.4"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021-184622"],"award-info":[{"award-number":["200021-184622"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021-165866"],"award-info":[{"award-number":["200021-165866"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["817750"],"award-info":[{"award-number":["817750"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1137\/20m135594x","type":"journal-article","created":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T18:36:41Z","timestamp":1634582201000},"page":"STOC20-24-STOC20-53","source":"Crossref","is-referenced-by-count":12,"title":["Reducing Path TSP to TSP"],"prefix":"10.1137","volume":"51","author":[{"given":"Vera","family":"Traub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2021,10,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/2818310"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/050645464"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9850-8"},{"key":"atypb4","unstructured":"N. Christofides,Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68279-0_14"},{"key":"atypb6","first-page":"104","volume-title":"Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems","author":"Feige U.","year":"2007"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.08.006"},{"key":"atypb9","first-page":"223","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Goemans M. X.","year":"1994"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1202-z"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.06.003"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00160-3"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56039-6"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2739008"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9439-7"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.94"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"atypb23","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790186704"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/3326123"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"atypb28","first-page":"76","volume":"17","author":"Serdjukov A. I.","year":"1978","journal-title":"Upravlyaemye Sistemy"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.09.009"},{"key":"atypb30","series-title":"SIAM J. Comput., to appear.","volume-title":"Beating the integrality ratio for $s$-$t$-tours in graphs","author":"Traub V."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/3309715"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/15M1010531"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0650"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.93"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M135594X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T20:47:08Z","timestamp":1709066828000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M135594X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,18]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/20M135594X"],"URL":"https:\/\/doi.org\/10.1137\/20m135594x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,18]]}}}