{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T06:12:26Z","timestamp":1761977546390,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450426"},{"type":"electronic","value":"9783642450433"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45043-3_2","type":"book-chapter","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T14:05:50Z","timestamp":1384265150000},"page":"5-11","source":"Crossref","is-referenced-by-count":2,"title":["Overview of New Approaches for Approximating TSP"],"prefix":"10.1007","author":[{"given":"Ola","family":"Svensson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: [18], pp. 550\u2013559","DOI":"10.1109\/FOCS.2011.80"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: [18], pp. 560\u2013569","DOI":"10.1109\/FOCS.2011.56"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Mucha, M.: 13\/9-approximation for graphic TSP. In: D\u00fcrr, C., Wilke, T. (eds.) STACS. LIPIcs, vol.\u00a014, pp. 30\u201341. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-32512-0_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Lampis","year":"2012","unstructured":"Lampis, M.: Improved inapproximability for TSP. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 243\u2013253. Springer, Heidelberg (2012)"},{"key":"2_CR5","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University (1976)"},{"issue":"5","key":"2_CR6","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"issue":"4","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing\u00a028(4), 1298\u20131309 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR8","unstructured":"Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Karloff, H.J. (ed.) SODA, pp. 33\u201341. ACM\/SIAM (1998)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.H.: An approximation scheme for planar graph TSP. In: Proc.\u00a036th Annual Symposium on Foundations of Computer Science (FOCS\u00a01995), pp. 640\u2013645. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"issue":"1","key":"2_CR10","first-page":"335","volume":"69","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Mathematics and Statistics\u00a069(1), 335\u2013349 (1995)","journal-title":"Mathematics and Statistics"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log n\/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In: Charikar, M. (ed.) SODA, pp. 379\u2013389. SIAM (2010)","DOI":"10.1137\/1.9781611973075.32"},{"issue":"2","key":"2_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(82)90059-7","volume":"19","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., J\u00e1j\u00e1, J.: On the relationship between the biconnectivity augmentation and travelling salesman problems. Theoretical Computer Science\u00a019(2), 189\u2013201 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01585735","volume":"46","author":"C.L. Monma","year":"1990","unstructured":"Monma, C.L., Munson, B.S., Pulleyblank, W.R.: Minimum-weight two-connected spanning networks. Mathematical Programming\u00a046(1), 153\u2013171 (1990)","journal-title":"Mathematical Programming"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-20807-2_6","volume-title":"Integer Programming and Combinatoral Optimization","author":"S. Boyd","year":"2011","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 65\u201377. Springer, Heidelberg (2011)"},{"issue":"5","key":"2_CR15","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.orl.2004.09.005","volume":"33","author":"D. Gamarnik","year":"2005","unstructured":"Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Operations Research Letters\u00a033(5), 467\u2013474 (2005)","journal-title":"Operations Research Letters"},{"key":"2_CR16","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for graphic TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. CoRR abs\/1201.1870 (2012)"},{"key":"2_CR17","unstructured":"Vygen, J.: New approximation algorithms for the TSP. In: OPTIMA, vol. 90, http:\/\/www.mathopt.org\/Optima-Issues\/optima90.pdf"},{"key":"2_CR18","unstructured":"Ostrovsky, R. (ed.): IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25. IEEE (2011)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45043-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T20:18:40Z","timestamp":1746044320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45043-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450426","9783642450433"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45043-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}