{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:09Z","timestamp":1740122469043,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s10878-020-00536-w","type":"journal-article","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T18:03:36Z","timestamp":1581703416000},"page":"1017-1037","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","volume":"39","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4908-7165","authenticated-orcid":false,"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":[[2020,2,14]]},"reference":[{"key":"536_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek A, Wiese A (2013) Approximation schemes for maximum weight independent set of rectangles. In: 2013 IEEE 54th annual symposium on foundations of computer science, pp 400\u2013409","DOI":"10.1109\/FOCS.2013.50"},{"key":"536_CR2","volume-title":"Network flows: theory, algorithms, and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice-Hall Inc., Upper Saddle River"},{"issue":"2","key":"536_CR3","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.comgeo.2012.04.001","volume":"47","author":"TM Chan","year":"2014","unstructured":"Chan TM, Grant E (2014) Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput Geom 47(2):112\u2013124","journal-title":"Comput Geom"},{"issue":"2","key":"536_CR4","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan TM, Har-Peled S (2012) Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput Geom 48(2):373\u2013392","journal-title":"Discrete Comput Geom"},{"issue":"5","key":"536_CR5","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.comgeo.2014.12.005","volume":"48","author":"TM Chan","year":"2015","unstructured":"Chan TM, Hu N (2015) Geometric red-blue set cover for unit squares and related problems. Comput Geom 48(5):380\u2013385","journal-title":"Comput Geom"},{"issue":"1","key":"536_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86(1):165\u2013177","journal-title":"Discrete Math"},{"key":"536_CR7","doi-asserted-by":"crossref","unstructured":"Dhar AK, Madireddy RR, Pandit S, Singh J (2019) Maximum independent and disjoint coverage. In: Theory and applications of models of computation (TAMC), pp. 134\u2013153","DOI":"10.1007\/978-3-030-14812-6_9"},{"issue":"6","key":"536_CR8","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 (2005) Polynomial-time approximation schemes for geometric intersection graphs. SIAM J Comput 34(6):1302\u20131323","journal-title":"SIAM J Comput"},{"key":"536_CR9","unstructured":"Erlebach T, van Leeuwen EJ (2008) Approximating geometric coverage problems. In: ACM-SIAM symposium on discrete algorithms (SODA), pp 1267\u20131276"},{"issue":"4","key":"536_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of $$\\ln n$$ for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"issue":"1","key":"536_CR11","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Maass W (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J ACM 32(1):130\u2013136","journal-title":"J ACM"},{"key":"536_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2014.04.014","volume":"544","author":"T Ito","year":"2014","unstructured":"Ito T, ichi Nakano S, Okamoto Y, Otachi Y, Uehara R, Uno T, Uno Y (2014) A 4.31-approximation for the geometric unique coverage problem on unit disks. Theor Comput Sci 544:14\u201331","journal-title":"Theor Comput Sci"},{"key":"536_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.comgeo.2015.10.004","volume":"51","author":"T Ito","year":"2016","unstructured":"Ito T, ichi Nakano S, Okamoto Y, Otachi Y, Uehara R, Uno T, Uno Y (2016) A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares. Comput Geom 51:25\u201339","journal-title":"Comput Geom"},{"key":"536_CR14","volume-title":"Algorithm design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg J, Tardos E (2006) Algorithm design. Addison Wesley, Boston"},{"key":"536_CR15","doi-asserted-by":"crossref","unstructured":"Madireddy RR, Mudgal A, Pandit S (2018) Hardness results and approximation schemes for discrete packing and domination problems. In: Conference on combinatorial optimization and applications (COCOA), pp 216\u2013226","DOI":"10.1007\/978-3-030-04651-4_28"},{"key":"536_CR16","unstructured":"Mehrabi S (2016) Geometric unique set cover on unit disks and unit squares. In: Canadian conference on computational geometry (CCCG), pp 195\u2013200"},{"issue":"2","key":"536_CR17","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer W, Rote G (2008) Minimum-weight triangulation is NP-hard. J ACM 55(2):11:1\u201311:29","journal-title":"J ACM"},{"key":"536_CR18","unstructured":"Nandy SC, Pandit S, Roy S (2017) Covering points: minimizing the maximum depth. In: Canadian conference on computational geometry (CCCG), pp 37\u201342"},{"key":"536_CR19","unstructured":"Nieberg T, Hurink J, Kern W (2005) A robust PTAS for maximum weight independent sets in unit disk graphs. In: Graph-theoretic concepts in computer science, pp 214\u2013221"},{"key":"536_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer TJ (1978) The complexity of satisfiability problems. In: ACM symposium on theory of computing (STOC), pp 216\u2013226","DOI":"10.1145\/800133.804350"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00536-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-020-00536-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00536-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T00:12:25Z","timestamp":1613261545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-020-00536-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,14]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["536"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00536-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,14]]},"assertion":[{"value":"14 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}