{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:20Z","timestamp":1725664520868},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620341"},{"type":"electronic","value":"9783540496311"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-62034-6_38","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:32:15Z","timestamp":1330295535000},"page":"64-75","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees"],"prefix":"10.1007","author":[{"given":"Gautam","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjiv","family":"Kapoor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"P.K. Agarwal","year":"1991","unstructured":"P.K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry 6 (1991), pp. 407\u2013422.","journal-title":"Discrete & Computational Geometry"},{"doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, to appear.","key":"6_CR2","DOI":"10.1109\/SFCS.1996.548458"},{"doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees. Proceedings 15th Annual ACM Symposium on the Theory of Computing, 1983, pp. 80\u201386.","key":"6_CR3","DOI":"10.1145\/800061.808735"},{"doi-asserted-by":"crossref","unstructured":"M.W. Bern, H.J. Karloff, P. Raghavan, and B. Schieber. Fast geometric approximation techniques and geometric embedding problems. Proceedings 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 292\u2013301.","key":"6_CR4","DOI":"10.1145\/73833.73866"},{"unstructured":"P.B. Callahan and S.R. Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. Proceedings 4th Annual Symposium on Discrete Algorithms, 1993, pp. 291\u2013300.","key":"6_CR5"},{"unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Report 388, Grad School of Industrial Administration, CMU, 1976.","key":"6_CR6"},{"unstructured":"J.H. van Lint and R.M. Wilson. A Course in Combinatorics. Cambridge University Press, 1992.","key":"6_CR7"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"C.H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science 4 (1977), pp. 237\u2013244.","journal-title":"Theoretical Computer Science"},{"key":"6_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry, an Introduction","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos. Computational Geometry, an Introduction. Springer-Verlag, New York, 1985."},{"key":"6_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J.S. Salowe","year":"1991","unstructured":"J.S. Salowe. Constructing multidimensional spanner graphs. International Journal of Computational Geometry and Applications 1 (1991), pp. 99\u2013107.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1137\/0217035","volume":"17","author":"P.M. Vaidya","year":"1988","unstructured":"P.M. Vaidya. Minimum spanning trees in k-dimensional space. SIAM Journal on Computing 17 (1988), pp. 572\u2013582.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62034-6_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:37:34Z","timestamp":1619573854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62034-6_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620341","9783540496311"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-62034-6_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}