{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:01Z","timestamp":1759638661429},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_11","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T18:35:59Z","timestamp":1464114959000},"page":"126-137","source":"Crossref","is-referenced-by-count":5,"title":["Better s-t-Tours by Gao Trees"],"prefix":"10.1007","author":[{"given":"Corinna","family":"Gottschalk","sequence":"first","affiliation":[]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the $$s$$ - $$t$$ path TSP. J. ACM 62, Article 34, 34:1\u201334:28 (2015)","DOI":"10.1145\/2818310"},{"key":"11_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)$$ -approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"11_CR3","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":"11_CR4","first-page":"B-73","volume":"13","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: The Chinese postman\u2019s problem. Bull. Oper. Res. Soc. Am. 13, B-73 (1965)","journal-title":"Bull. Oper. Res. Soc. Am."},{"key":"11_CR5","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":"11_CR6","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}$$ -approximation algorithm for the $$s$$ - $$t$$ path graph traveling salesman problem. Oper. Res. Lett. 41, 615\u2013617 (2013)","journal-title":"Oper. Res. Lett."},{"key":"11_CR7","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$$ - $$t$$ path traveling salesman problem. SIAM J. Discrete Math. 29, 1133\u20131149 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/978-3-662-48350-3_48","volume-title":"Algorithms \u2013 ESA 2015","author":"K Genova","year":"2015","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 \u2013 ESA 2015. LNCS, pp. 570\u2013581. Springer, Heidelberg (2015)"},{"key":"11_CR9","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 2006), pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"11_CR10","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":"11_CR11","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":"11_CR12","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":"11_CR13","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 2011), pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Seb\u0151","year":"2013","unstructured":"Seb\u0151, A.: Eight-fifth approximation for the path TSP. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 362\u2013374. Springer, Heidelberg (2013)"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u00f6","year":"2014","unstructured":"Seb\u00f6, 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":"11_CR16","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":"11_CR17","unstructured":"Vygen, J.: Reassembling trees for the traveling salesman. SIAM J. Discrete Math. To appear. arXiv:1502.03715"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T15:46:32Z","timestamp":1567957592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}