{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:43:44Z","timestamp":1742395424796},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662006"},{"type":"electronic","value":"9783540486862"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_47","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:12Z","timestamp":1184601252000},"page":"473-482","source":"Crossref","is-referenced-by-count":7,"title":["A Fast Approximation Algorithm for TSP with Neighborhoods and Red-Blue Separation"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"47_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E. M. Arkin","year":"1994","unstructured":"E. M. Arkin and R. Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Math, 55:197\u2013218, 1994.","journal-title":"Discrete Applied Math"},{"key":"47_CR2","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF01769706","volume":"10","author":"E. M. Arkin","year":"1993","unstructured":"E. M. Arkin, S. Khuller, and J. S. B. Mitchell. Geometric knapsack problems. Algoritmica, 10:399\u2013427, 1993.","journal-title":"Algoritmica"},{"key":"47_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In FOCS'96, pages 2\u201311, 1996.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"47_CR4","first-page":"02418","volume-title":"Minimum edge length guillotine rectangular partition","author":"D. Z. Du","year":"1986","unstructured":"D. Z. Du, L. Q. Pan, and M. T. Shing. Minimum edge length guillotine rectangular partition. Technical Report 02418\u201386, Math. Sci. Res. Inst., University of California, Berkeley, CA, 1986."},{"key":"47_CR5","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/0167-8655(93)90140-9","volume":"14","author":"P. Eades","year":"1993","unstructured":"P. Eades and D. Rappaport. The complexity of computing minimum separating polygons. Pattern Recognition Letters, 14:715\u2013718, 1993.","journal-title":"Pattern Recognition Letters"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"M. R. Garey, R. L. Graham, and D. S. Johnson. Some NP-complete geometric problems. In STOC'76, pages 10\u201321, 1976.","DOI":"10.1145\/800113.803626"},{"key":"47_CR7","doi-asserted-by":"crossref","unstructured":"T. Gonzalez and S. Q. Zheng. Bound for partitioning rectilinear polygons. In SoCG'85, pages 281\u2013287, 1985.","DOI":"10.1145\/323233.323269"},{"key":"47_CR8","volume-title":"A fast approximation algorithm for TSP with neighborhoods and red-blue separation","author":"J. Gudmundsson","year":"1997","unstructured":"J. Gudmundsson and C. Levcopoulos. A fast approximation algorithm for TSP with neighborhoods and red-blue separation. Technical Report LU-CS-TR:97-196, Dept. of Computer Science, Lund University, Lund, Sweden, 1997."},{"key":"47_CR9","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J. Hershberger","year":"1995","unstructured":"J. Hershberger and S. Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18:403\u2013431, 1995.","journal-title":"Journal of Algorithms"},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos. Fast heuristics for minimum length rectangular partitions of polygons. In SoCG'86, pages 100\u2013108, 1986.","DOI":"10.1145\/10515.10526"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"C. S. Mata and J. S. B. Mitchell. Approximation algorithms for geometric tour and network design problems. In SoCG'95, pages 360\u2013369, 1995.","DOI":"10.1145\/220279.220318"},{"key":"47_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C. H. Papadimitriou","year":"1977","unstructured":"C. H. Papadimitriou. Euclidean TSP is NP-complete. TCS, 4:237\u2013244, 1977.","journal-title":"TCS"},{"key":"47_CR13","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, NY, 1985."},{"key":"47_CR14","series-title":"Lect Notes Comput Sci","first-page":"196","volume-title":"Proceedings of the 15th International Workshop Graph-Theoretical Concepts in Computer Science","author":"G. Reich","year":"1989","unstructured":"G. Reich and P. Widmayer. Beyond steiner\u2019s problem: A vlsi oriented generalization. In Proceedings of the 15th International Workshop Graph-Theoretical Concepts in Computer Science, volume 411 of LNCS, pages 196\u2013210, 1989."},{"key":"47_CR15","series-title":"NATO ASI","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-83539-1_9","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"M. Sharir","year":"1988","unstructured":"M. Sharir. Davenport-schinzel sequences and their geometric applications. In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD, volume F40 of NATO ASI, pages 253\u2013278. Springer-Verlag, Berlin, Germany, 1988."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:13:40Z","timestamp":1556680420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_47","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}