{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T06:02:40Z","timestamp":1746252160695},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,10,27]],"date-time":"2017-10-27T00:00:00Z","timestamp":1509062400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-017-1202-z","type":"journal-article","created":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T23:40:27Z","timestamp":1509061227000},"page":"191-207","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Better s\u2013t-tours by Gao trees"],"prefix":"10.1007","volume":"172","author":[{"given":"Corinna","family":"Gottschalk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,27]]},"reference":[{"key":"1202_CR1","first-page":"34","volume":"62","author":"H-C An","year":"2015","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the $$s$$ s \u2013 $$t$$ t path TSP. J. ACM 62, 34 (2015)","journal-title":"J. ACM"},{"key":"1202_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., M\u0105dry, A., Oveis Gharan, S., Saberi, A. : An $$O(\\log n\/\\log \\log n)$$ O ( log n \/ log log n ) -approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"1202_CR3","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/s00453-013-9850-8","volume":"72","author":"J Cheriyan","year":"2015","unstructured":"Cheriyan, J., Friggstad, Z., Gao, Z.: Approximating minimum-cost connected $$T$$ T -joins. Algorithmica 72, 126\u2013147 (2015)","journal-title":"Algorithmica"},{"key":"1202_CR4","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976)"},{"key":"1202_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"WH Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. J. Comb. Theory B 36, 161\u2013188 (1984)","journal-title":"J. Comb. Theory B"},{"key":"1202_CR6","unstructured":"Edmonds, J.: The Chinese postman\u2019s problem. Bull. Op. Res. Soc. Am. 13, B-73 (1965)"},{"key":"1202_CR7","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"1202_CR8","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/j.orl.2013.08.006","volume":"41","author":"Z Gao","year":"2013","unstructured":"Gao, Z.: An LP-based $$\\frac{3}{2}$$ 3 2 -approximation algorithm for the $$s$$ s \u2013 $$t$$ t path graph traveling salesman problem. Oper. Res. Lett. 41, 615\u2013617 (2013)","journal-title":"Oper. Res. Lett."},{"key":"1202_CR9","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/14096712X","volume":"29","author":"Z Gao","year":"2015","unstructured":"Gao, Z.: On the metric $$s$$ s - $$t$$ t path traveling salesman problem. SIAM J. Discret. Math. 29, 1133\u20131149 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"1202_CR10","doi-asserted-by":"crossref","unstructured":"Genova, K., Williamson, D.P.: An experimental evaluation of the best-of-many Christofides\u2019 algorithm for the traveling salesman problem. In: Bansal, N., Finocchi, I. (eds.) Algorithms\u2013ESA 2015; LNCS 9294, pp. 570\u2013581. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48350-3_48"},{"key":"1202_CR11","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"1202_CR12","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"1202_CR13","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138\u20131162 (1970)","journal-title":"Oper. Res."},{"key":"1202_CR14","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"JA Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10, 291\u2013295 (1991)","journal-title":"Oper. Res. Lett."},{"key":"1202_CR15","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"1202_CR16","unstructured":"Schalekamp, F., Seb\u0151, A., Traub, V., van Zuylen, A.: Layers and matroids for the traveling salesman\u2019s paths. arXiv:1703.07170"},{"key":"1202_CR17","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A.: Eight fifth approximation for TSP paths. In: Correa, J.,\u00a0Goemans, M.X. (eds.) Proceedings of the 16th IPCO Conference; LNCS 7801, Integer Programming and Combinatorial Optimization, pp. 362\u2013374. Springer (2013)","DOI":"10.1007\/978-3-642-36694-9_31"},{"key":"1202_CR18","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34, 597\u2013629 (2014)","journal-title":"Combinatorica"},{"key":"1202_CR19","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., van Zuylen, A.: The salesman\u2019s improved paths: 3\/2\u00a0+\u00a01\/34 integrality gap and approximation ratio. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 118\u2013127","DOI":"10.1109\/FOCS.2016.21"},{"key":"1202_CR20","unstructured":"Traub, V., Vygen, J.: Approaching $$\\frac{3}{2}$$ 3 2 for the $$s$$ s - $$t$$ t -path TSP. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (2018) (to appear)"},{"key":"1202_CR21","first-page":"1","volume":"90","author":"J Vygen","year":"2012","unstructured":"Vygen, J.: New approximation algorithms for the TSP. OPTIMA 90, 1\u201312 (2012)","journal-title":"OPTIMA"},{"key":"1202_CR22","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/15M1010531","volume":"30","author":"J Vygen","year":"2016","unstructured":"Vygen, J.: Reassembling trees for the traveling salesman. SIAM J. Discrete Math. 30, 875\u2013894 (2016)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1202-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1202-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1202-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T02:46:17Z","timestamp":1570243577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1202-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,27]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1202"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1202-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,27]]}}}