{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:07Z","timestamp":1771036387706,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642360640","type":"print"},{"value":"9783642360657","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36065-7_10","type":"book-chapter","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T16:36:53Z","timestamp":1358786213000},"page":"89-100","source":"Crossref","is-referenced-by-count":11,"title":["Approximation Schemes for Covering and Packing"],"prefix":"10.1007","author":[{"given":"Rom","family":"Aschner","sequence":"first","affiliation":[]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[]},{"given":"Gila","family":"Morgenstern","sequence":"additional","affiliation":[]},{"given":"Yelena","family":"Yuditsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: Proc. 22nd ACM Sympos. on Theory of Computing, pp. 293\u2013299 (1990)","DOI":"10.1145\/100216.100254"},{"issue":"1","key":"10_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"7","key":"10_CR3","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.comgeo.2012.01.014","volume":"45","author":"S. Bereg","year":"2012","unstructured":"Bereg, S., Cabello, S., D\u00edaz-B\u00e1\u00f1ez, J.M., P\u00e9rez-Lantero, P., Seara, C., Ventura, I.: The class cover problem with boxes. Comput. Geom. Theory Appl.\u00a045(7), 294\u2013304 (2012)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms\u00a046(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"10_CR5","unstructured":"Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. Theory Appl. (in press, available online)"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proc. 25th ACM Sympos. on Computational Geometry, pp. 333\u2013340 (2009)","DOI":"10.1145\/1542362.1542420"},{"key":"10_CR7","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proc. 7th Canadian Conf. on Computational Geometry, pp. 133\u2013138 (1995)"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.ipl.2006.05.014","volume":"100","author":"A. Efrat","year":"2006","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett.\u00a0100, 238\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S. Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica\u00a031(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J.: Separator theorems and Turan-type results for planar intersection graphs. In: Advances in Mathematics, vol.\u00a0219, pp. 1070\u20131080 (2009)","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"6","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs. SIAM Journal on Computing\u00a06, 1004\u20131022 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR12","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Proc. Canadian Inform. Process. Soc. Congress, pp. 429\u2013434 (1987)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-03685-9_11","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Gibson","year":"2009","unstructured":"Gibson, M., Kanade, G., Krohn, E., Varadarajan, K.: An Approximation Scheme for Terrain Guarding. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 140\u2013148. Springer, Heidelberg (2009)"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-15775-2_21","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Gibson","year":"2010","unstructured":"Gibson, M., Pirwani, I.A.: Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 243\u2013254. Springer, Heidelberg (2010)"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"King, J., Krohn, E.: Terrain guarding is NP-hard. In: Proc. 21st ACM-SIAM Sympos. on Discrete Algorithms, pp. 1580\u20131593 (2010)","DOI":"10.1137\/1.9781611973075.128"},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W.P., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"N.H. Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete & Computational Geometry\u00a044(4), 883\u2013895 (2010)","journal-title":"Discrete & Computational Geometry"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Smith, W.D., Wormald, N.C.: Geometric separator theorems & applications. In: Proc. IEEE 39th Sympos. on Foundations of Computer Science, pp. 232\u2013243 (1998)","DOI":"10.1109\/SFCS.1998.743449"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36065-7_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T17:54:11Z","timestamp":1745949251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36065-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360640","9783642360657"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36065-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}