{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T22:10:06Z","timestamp":1748815806256,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_52","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"700-711","source":"Crossref","is-referenced-by-count":0,"title":["Independent Set of Convex Polygons: From $$n^{\\epsilon }$$ n \u03f5 to $$1+\\epsilon $$ 1 + \u03f5 via Shrinking"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Wiese","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"52_CR1","unstructured":"Adamaszek, A., Chalermsook, P., Wiese, A.: How to tame rectangles: solving independent set and coloring of rectangles via shrinking. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 43\u201360. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2015)"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS ), pp. 400\u2013409. IEEE (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 645\u2013656. SIAM (2014)","DOI":"10.1137\/1.9781611973402.49"},{"issue":"2","key":"52_CR4","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.comgeo.2005.12.001","volume":"34","author":"PK Agarwal","year":"2006","unstructured":"Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2D. Comput. Geom. 34(2), 83\u201395 (2006)","journal-title":"Comput. Geom."},{"key":"52_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11, 209\u2013218 (1998)","journal-title":"Comput. Geom."},{"key":"52_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-36694-9_3","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Anagnostopoulos","year":"2013","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: Constant integrality gap LP formulations of unsplittable flow on a path. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 25\u201336. Springer, Heidelberg (2013)"},{"issue":"2","key":"52_CR7","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1006\/jagm.2001.1188","volume":"41","author":"P Berman","year":"2001","unstructured":"Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. J. Algor. 41(2), 443\u2013470 (2001)","journal-title":"J. Algor."},{"key":"52_CR8","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: Proceedings of the 52th Annual IEEE Symposium on Foundations of Computer Science (FOCS ), pp. 47\u201356 (2011)","DOI":"10.1109\/FOCS.2011.10"},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 892\u2013901. SIAM (2009)","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"52_CR10","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Comput. Geom. 48(2), 373\u2013392 (2012)","journal-title":"Discrete & Comput. Geom."},{"issue":"1","key":"52_CR11","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"de Floriani, L., Magillo, P., Puppo, E.: Applications of computational geometry to geographic information systems. In: Handbook of Computational Geometry, pp. 333\u2013388. North Holland (2000)","DOI":"10.1016\/B978-044482537-7\/50008-5"},{"issue":"6","key":"52_CR13","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34(6), 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"52_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J.: Computing the independence number of intersection graphs. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1161\u20131165. SIAM (2011)","DOI":"10.1137\/1.9781611973082.87"},{"issue":"2","key":"52_CR16","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1145\/383891.383893","volume":"26","author":"T Fukuda","year":"2001","unstructured":"Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data mining with optimized two-dimensional association rules. ACM Trans. Database Syst. (TODS) 26(2), 179\u2013213 (2001)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG), pp. 120\u2013129. ACM (2014)","DOI":"10.1145\/2582112.2582157"},{"key":"52_CR18","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"4","key":"52_CR19","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H Imai","year":"1983","unstructured":"Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algor. 4(4), 310\u2013323 (1983)","journal-title":"J. Algor."},{"key":"52_CR20","unstructured":"Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384\u2013393. SIAM (1998)"},{"key":"52_CR21","doi-asserted-by":"crossref","unstructured":"Lent, B., Swami, A., Widom, J.: Clustering association rules. In: Proceedings of the 13th International Conference on Data Engineering, pp. 220\u2013231. IEEE (1997)","DOI":"10.1109\/ICDE.1997.581756"},{"key":"52_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0304-3975(98)00336-3","volume":"246","author":"F Nielsen","year":"2000","unstructured":"Nielsen, F.: Fast stabbing of boxes in high dimensions. Theor. Comp. Sc. 246, 53\u201372 (2000)","journal-title":"Theor. Comp. Sc."},{"key":"52_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-48481-7_37","volume-title":"Algorithms - ESA\u201999","author":"B Verweij","year":"1999","unstructured":"Verweij, B., Aardal, K.: An optimisation algorithm for maximum independent set with applications in map labelling. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 426\u2013437. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T21:29:23Z","timestamp":1748813363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}