{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T08:43:50Z","timestamp":1772009030871,"version":"3.50.1"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030148119","type":"print"},{"value":"9783030148126","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-14812-6_9","type":"book-chapter","created":{"date-parts":[[2019,4,9]],"date-time":"2019-04-09T23:44:24Z","timestamp":1554853464000},"page":"134-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Maximum Independent and Disjoint Coverage"],"prefix":"10.1007","author":[{"given":"Amit Kumar","family":"Dhar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghunath Reddy","family":"Madireddy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Supantha","family":"Pandit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jagpreet","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,6]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pp. 400\u2013409 (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"9_CR2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc., Upper Saddle River (1993)"},{"issue":"2","key":"9_CR3","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.comgeo.2012.04.001","volume":"47","author":"TM Chan","year":"2014","unstructured":"Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. 47(2), 112\u2013124 (2014)","journal-title":"Comput. Geom."},{"issue":"2","key":"9_CR4","doi-asserted-by":"crossref","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":"5","key":"9_CR5","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.comgeo.2014.12.005","volume":"48","author":"TM Chan","year":"2015","unstructured":"Chan, T.M., Hu, N.: Geometric red-blue set cover for unit squares and related problems. Comput. Geom. 48(5), 380\u2013385 (2015)","journal-title":"Comput. Geom."},{"issue":"1","key":"9_CR6","doi-asserted-by":"crossref","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."},{"issue":"6","key":"9_CR7","doi-asserted-by":"crossref","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."},{"key":"9_CR8","unstructured":"Erlebach, T., van Leeuwen, E.J.: Approximating geometric coverage problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 1267\u20131276 (2008)"},{"issue":"4","key":"9_CR9","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9_CR10","doi-asserted-by":"crossref","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(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2014.04.014","volume":"544","author":"T Ito","year":"2014","unstructured":"Ito, T., et al.: A 4.31-approximation for the geometric unique coverage problem on unit disks. Theor. Comput. Sci. 544, 14\u201331 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.comgeo.2015.10.004","volume":"51","author":"T Ito","year":"2016","unstructured":"Ito, T., et al.: A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares. Comput. Geom. 51, 25\u201339 (2016)","journal-title":"Comput. Geom."},{"key":"9_CR13","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Addison Wesley, Boston (2006)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-030-04651-4_28","volume-title":"Combinatorial Optimization and Applications","author":"RR Madireddy","year":"2018","unstructured":"Madireddy, R.R., Mudgal, A., Pandit, S.: Hardness results and approximation schemes for discrete packing and domination problems. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 421\u2013435. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04651-4_28"},{"key":"9_CR15","unstructured":"Mehrabi, S.: Geometric unique set cover on unit disks and unit squares. In: Proceedings of the 28th Canadian Conference on Computational Geometry, CCCG 2016, pp. 195\u2013200 (2016)"},{"issue":"2","key":"9_CR16","doi-asserted-by":"crossref","first-page":"11:1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 11:1\u201311:29 (2008)","journal-title":"J. ACM"},{"key":"9_CR17","unstructured":"Nandy, S.C., Pandit, S., Roy, S.: Covering points: Minimizing the maximum depth. In: Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, pp. 37\u201342 (2017)"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-540-30559-0_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T Nieberg","year":"2004","unstructured":"Nieberg, T., Hurink, J., Kern, W.: A robust PTAS for maximum weight independent sets in unit disk graphs. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 214\u2013221. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30559-0_18"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-14812-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:08:12Z","timestamp":1709824092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-14812-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030148119","9783030148126"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-14812-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"6 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kitakyushu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}