{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:42:58Z","timestamp":1725486178780},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_2","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"16-17","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Schemes for Geometric NP-Hard Problems: A Survey"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. JACM 45(5) 753\u2013782, 1998. Preliminary versions in Proceedings of 37th IEEE Symp. on Foundations of Computer Science, 1996, and Proceedings of 38th IEEE Symp. on Foundations of Computer Science, 1997.","journal-title":"JACM"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora and G. Karakostas. Approximation schemes for minimum latency problems. Proc. ACM Symposium on Theory of Computing, 1999.","DOI":"10.1145\/301250.301432"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclidean k-medians andrelatedproblems. In In Proc. 30th ACM Symposium on Theory of Computing, pp 106\u2013113, 1998.","DOI":"10.1145\/276698.276718"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"T. Asano, N. Katoh, H. Tamaki and T. Tokuyama. Covering Points in the Plane by k-Tours: Towards a Polynomial Time Approximation Scheme for General k. In Proc. 29th Annual ACM Symposium on Theory of Computing, pp 275\u2013283, 1997.","DOI":"10.1145\/258533.258602"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"A. Barvinok, S. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, R. Woodroofe. The maximum traveling salesman problem. Merger of two papers in Proc. IPCO 1998 and Proc. ACM-SIAM SODA 1998.","DOI":"10.1007\/3-540-69346-7_15"},{"key":"2_CR6","unstructured":"M. Bern and D. Eppstein. Approximation algorithms for geometric problems. In [10]."},{"key":"2_CR7","unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. In J.F. Traub, editor, Symposium on new directions and recent results in algorithms and complexity, page 441. Academic Press, NY, 1976."},{"key":"2_CR8","series-title":"Lect Notes Comput Sci","volume-title":"A polynomial time approximation scheme for Euclidean minimum cost k-connectivity","author":"A. Czumaj","year":"1998","unstructured":"A. Czumaj and A. Lingas. A polynomial time approximation scheme for Euclidean minimum cost k-connectivity. Proc. 25th Annual International Colloquium on Automata, Languages and Programming, LNCS, Springer Verlag 1998."},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"W. Fernandez de la Vega and C. Kenyon. A randomized approximation scheme for metric MAX-CUT. Proc. 39th IEEE Symp. on Foundations of Computer Science, pp 468\u2013471, 1998.","DOI":"10.1109\/SFCS.1998.743497"},{"volume-title":"Approximation Algorithms for NP-hard problems","year":"1996","key":"2_CR10","unstructured":"D. Hochbaum, ed. Approximation Algorithms for NP-hard problems. PWS Publishing, Boston, 1996."},{"key":"2_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/3-540-48481-7_33","volume-title":"A nearly linear time approximation scheme for the Euclidean k-median problem","author":"S. G. Kolliopoulos","year":"1999","unstructured":"S. G. Kolliopoulos and S. Rao. A nearly linear time approximation scheme for the Euclidean k-median problem. LNCS, vol.1643, pp 378\u2013387, 1999."},{"key":"2_CR12","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. The traveling salesman problem. John Wiley, 1985"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple PTAS for geometric k-MST, TSP, andrelatedproblems. SIAM J. Comp., 28, 1999. Preliminary manuscript, April 30, 1996. To appear in SIAM J. Computing.","DOI":"10.1137\/S0097539796309764"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"S. Rao and W. Smith. Approximating geometric graphs via \u201cspanners\u201d and \u201cbanyans.\u201d In Proc. 30th ACM Symposium on Theory of Computing, pp. 540\u2013550, 1998.","DOI":"10.1145\/276698.276868"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A.Z. Zelikovsky","year":"1993","unstructured":"A.Z. Zelikovsky. An 11\/6-approximation algorithm for the network Steiner Problem. Algorithmica, 9:463\u2013470, 1993.","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:28:02Z","timestamp":1556501282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}