{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:01:53Z","timestamp":1725487313394},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_16","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"176-188","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin L.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"16_CR1","unstructured":"Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of 37th IEEE Symp. on Foundations of Computer Science, 1996."},{"issue":"5","key":"16_CR2","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.","journal-title":"JACM"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. Math Programming, 2003 (to appear). Available from www.cs.princeton.edu\/~arora.","DOI":"10.1007\/s10107-003-0438-y"},{"key":"16_CR4","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":"16_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclidean k-medians and related problems. In Proc. 30th ACM Symposium on Theory of Computing, pp 106\u2013113, 1998.","DOI":"10.1145\/276698.276718"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. Proc. Cambridge Philos. Soc. 55:299\u2013327, 1959.","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"16_CR7","volume-title":"Approximation Algorithms for NP-hard problems","author":"M. Bern","year":"1996","unstructured":"M. Bern and D. Eppstein. Approximation algorithms for geometric problems. In [9]."},{"key":"16_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Proc. 25th Annual International Colloquium on Automata, Languages and Programming","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."},{"volume-title":"Approximation Algorithms for NP-hard problems","year":"1996","key":"16_CR9","unstructured":"D. Hochbaum, ed. Approximation Algorithms for NP-hard problems. PWS Publishing, Boston, 1996."},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/S0097539794264585","volume":"25","author":"S. Khuller","year":"1996","unstructured":"S. Khuller, B. Raghavachari, and N. Young. Low degree spanning tree of small weight. SIAM J. Computing, 25:355\u2013368, 1996. Preliminary version in Proc. 26th ACM Symposium on Theory of Computing, 1994.","journal-title":"SIAM J. Computing"},{"key":"16_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":"16_CR12","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. The traveling salesman problem. John Wiley, 1985"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"C.S. Mata and J. Mitchell. Approximation Algorithms for Geometric tour and network problems. In Proc. 11th ACM Symp. Comp. Geom., pp 360\u2013369, 1995.","DOI":"10.1145\/220279.220318"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple PTAS for geometric k-MST, TSP, and related problems. SIAM J. Comp., 28, 1999. Preliminary manuscript, April 30, 1996. To appear in SIAM J. Computing.","DOI":"10.1137\/S0097539796309764"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the traveling salesman problem. J. Algorithms 5(1984), pp. 231\u2013246.","journal-title":"J. Algorithms"},{"key":"16_CR16","volume-title":"Approximation Algorithms for NP-hard problems","author":"B. Raghavachari","year":"1996","unstructured":"B. Raghavachari. Algorithms for finding low degree structures. In [9]"},{"key":"16_CR17","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"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:14:31Z","timestamp":1556680471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}