{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:52:08Z","timestamp":1725688328814},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_20","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"225-236","source":"Crossref","is-referenced-by-count":2,"title":["A Probabilistic Analysis of Christofides\u2019 Algorithm"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstatinos","family":"Panagiotou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"20_CR1","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. J. ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"02","key":"20_CR2","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1017\/S0269964800000711","volume":"2","author":"D. Avis","year":"1988","unstructured":"Avis, D., Davis, B., Steele, J.M.: Probabilistic analysis of a greedy heuristic for euclidean matching. Probability in the Engineering and Informational Sciences\u00a02(02), 143\u2013156 (1988)","journal-title":"Probability in the Engineering and Informational Sciences"},{"issue":"1-2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1002\/rsa.20156","volume":"30","author":"A. Baltz","year":"2007","unstructured":"Baltz, A., Dubhashi, D.P., Srivastav, A., Tansini, L., Werth, S.: Probabilistic analysis for a multiple depot vehicle routing problem. Random Struct. Algorithms\u00a030(1-2), 206\u2013225 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"Beardwood, J., Halton, J.H., Hammersley, J.M.: The shortest path through many points. Proc. Cambridge Philos. Soc.\u00a055, 299\u2013327 (1959)","journal-title":"Proc. Cambridge Philos. Soc."},{"issue":"4","key":"20_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6377(90)90066-E","volume":"9","author":"D.J. Bertsimas","year":"1990","unstructured":"Bertsimas, D.J., van Ryzin, G.: An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability. Operations Research Letters\u00a09(4), 223\u2013231 (1990)","journal-title":"Operations Research Letters"},{"key":"20_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"20_CR7","first-page":"6","volume":"14","author":"V. Deineko","year":"2010","unstructured":"Deineko, V., Tiskin, A.: Fast minimum-weight double-tree shortcutting for metric tsp: Is the best one good enough? J. Exp. Algorithmics 14, 4.6\u20134.16 (2010)","journal-title":"J. Exp. Algorithmics"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Yukich, J.E.: Probabilistic analysis of the traveling salesman problem. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and Its Variations, pp. 257\u2013308. Kluwer Academic Publisher (2002)","DOI":"10.1007\/0-306-48213-4_7"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1287\/moor.16.1.72","volume":"16","author":"M.X. Goemans","year":"1991","unstructured":"Goemans, M.X., Bertsimas, D.J.: Probabilistic analysis of the held and karp lower bound for the euclidean traveling salesman problem. Mathematics of Operations Research\u00a016(1), 72\u201389 (1991)","journal-title":"Mathematics of Operations Research"},{"key":"20_CR10","unstructured":"Gutin, G., Punnen, A.P. (eds.): The traveling salesman problem and its variations. Combinatorial Optimization, vol.\u00a012. Kluwer Academic Publishers (2002)"},{"key":"20_CR11","unstructured":"Johnson, D.S., McGeoch, L.A., Rothberg, E.E.: Asymptotic experimental analysis for the held-karp traveling salesman bound. In: SODA 1996, pp. 341\u2013350 (1996)"},{"issue":"3","key":"20_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"Karp, R.M.: Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. of Operat. Research\u00a02(3), 209\u2013224 (1977)","journal-title":"Math. of Operat. Research"},{"issue":"4","key":"20_CR13","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J. Mitchell","year":"1999","unstructured":"Mitchell, J.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput.\u00a028(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/rsa.3240030302","volume":"3","author":"W.T. Rhee","year":"1992","unstructured":"Rhee, W.T.: On the travelling salesperson problem in many dimensions. Random Struct. Algorithms\u00a03(3), 227\u2013234 (1992)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"20_CR15","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1214\/aoap\/1177005364","volume":"3","author":"W.T. Rhee","year":"1993","unstructured":"Rhee, W.T.: A matching problem and subadditive euclidean functionals. Ann. Appl. Probab.\u00a03(3), 794\u2013801 (1993)","journal-title":"Ann. Appl. Probab."},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J.M. Steele","year":"1981","unstructured":"Steele, J.M.: Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab.\u00a09(3), 365\u2013376 (1981)","journal-title":"Ann. Probab."},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1214\/aop\/1176991596","volume":"16","author":"J.M. Steele","year":"1988","unstructured":"Steele, J.M.: Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab.\u00a016, 1767\u20131787 (1988)","journal-title":"Ann. Probab."},{"key":"20_CR18","unstructured":"Steele, J.M.: Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a069. SIAM (1997)"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol.\u00a01675. Springer (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:31Z","timestamp":1620128911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}