{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T19:29:42Z","timestamp":1771788582397,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Department of Science and Technology, Ministry of Science and Technology","award":["project DSTO-1209"],"award-info":[{"award-number":["project DSTO-1209"]}]},{"name":"European Research Council","award":["306992"],"award-info":[{"award-number":["306992"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00224-021-10050-z","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T10:04:02Z","timestamp":1626861842000},"page":"89-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exact Multi-Covering Problems with Geometric Sets"],"prefix":"10.1007","volume":"66","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"10050_CR1","doi-asserted-by":"crossref","unstructured":"Ashok, P., Kolay, S., Misra, N., Saurabh, S.: Unique covering problems with geometric sets International Computing and Combinatorics Conference, pp. 548\u2013558. Springer (2015)","DOI":"10.1007\/978-3-319-21398-9_43"},{"issue":"2","key":"10050_CR2","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/s10878-019-00432-y","volume":"39","author":"P Ashok","year":"2020","unstructured":"Ashok, P., Roy, A.B., Govindarajan, S.: Local search strikes again: Ptas for variants of geometric covering and packing. J. Comb. Optim. 39(2), 618\u2013635 (2020)","journal-title":"J. Comb. Optim."},{"key":"10050_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: European Symposium on Algorithms, pages 145\u2013156. Springer (2012)","DOI":"10.1007\/978-3-642-33090-2_14"},{"issue":"1","key":"10050_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms (TALG) 9(1), 1\u201317 (2012)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"4","key":"10050_CR5","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1137\/060656048","volume":"38","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Feige, U., Hajiaghayi, M.-T., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput. 38(4), 1464\u20131483 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10050_CR6","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"10050_CR7","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity, p 530. Springer, Berlin (1999)"},{"issue":"1","key":"10050_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"10050_CR9","volume-title":"Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus (2006)"},{"issue":"3","key":"10050_CR10","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":"10050_CR11","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC \u201974, pp. 47\u201363. New York, NY. ACM, USA (1974)","DOI":"10.1145\/800119.803884"},{"issue":"1","key":"10050_CR12","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(86)90016-8","volume":"15","author":"NG Hall","year":"1986","unstructured":"Hall, N.G, Hochbaum, D.S: A fast approximation algorithm for the multicovering problem. Discret. Appl. Math. 15(1), 35\u201340 (1986)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"10050_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0377-2217(92)90122-P","volume":"62","author":"NG Hall","year":"1992","unstructured":"Hall, N.G, Hochbaum, D.S: The multicovering problem. Eur. J. Oper. Res. 62(3), 323\u2013339 (1992)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"10050_CR14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(87)90012-5","volume":"8","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S, Maass, W.: Fast approximation algorithms for a nonconvex covering problem. J. Algorithms 8(3), 305\u2013323 (1987)","journal-title":"J. Algorithms"},{"key":"10050_CR15","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., Nakano, Shin-ichi, Okamoto, Y., Otachi, Y., Uehara, R., Uno, T., Uno, Y.: 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":"10050_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Complex. Comput. Comput., 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10050_CR17","doi-asserted-by":"crossref","unstructured":"Anil Kumar, V.S., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: International Colloquium on Automata, Languages, and Programming, pp. 624\u2013635. Springer (2000)","DOI":"10.1007\/3-540-45022-X_53"},{"issue":"4","key":"10050_CR18","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00454-004-1108-4","volume":"33","author":"S Langerman","year":"2005","unstructured":"Langerman, S., Morin, P.: Covering things with things. Discrete Comput. Geom. 33(4), 717\u2013729 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"10050_CR19","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems?. In: ESA, pp 448\u2013459. Springer (2005)","DOI":"10.1007\/11561071_41"},{"key":"10050_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13-15, 2006, Proceedings, pp. 154\u2013165 (2006)","DOI":"10.1007\/11847250_14"},{"key":"10050_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on discrete geometry, vol. 108","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on discrete geometry, vol. 108. Springer, New York (2002)"},{"issue":"5","key":"10050_CR22","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1(5), 194\u2013197 (1982)","journal-title":"Oper. Res. Lett."},{"key":"10050_CR23","doi-asserted-by":"crossref","unstructured":"Misra, N., Moser, H., Raman, V., Saurabh, S., Sikdar, S.: The parameterized complexity of unique coverage and its variants. Algorithmica, 517\u2013544 (2013)","DOI":"10.1007\/s00453-011-9608-0"},{"key":"10050_CR24","doi-asserted-by":"crossref","unstructured":"Mustafa, N., Ray, S.: Ptas for geometric hitting set problems via local search. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 17\u201322. ACM (2009)","DOI":"10.1145\/1542362.1542367"},{"issue":"1","key":"10050_CR25","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/BF02523687","volume":"18","author":"D Peleg","year":"1997","unstructured":"Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica 18(1), 44\u201366 (1997)","journal-title":"Algorithmica"},{"issue":"2","key":"10050_CR26","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N, Ya Chervonenkis, A.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10050-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10050-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10050-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T04:37:34Z","timestamp":1643344654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10050-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10050"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10050-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"24 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}