{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T09:39:06Z","timestamp":1777628346897,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"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,2]]},"DOI":"10.1007\/s10878-019-00432-y","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T14:03:03Z","timestamp":1561125783000},"page":"618-635","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Local search strikes again: PTAS for variants of geometric covering and packing"],"prefix":"10.1007","volume":"39","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9140-9167","authenticated-orcid":false,"given":"Aniket","family":"Basu Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sathish","family":"Govindarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"key":"432_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal PK, Pach J, Sharir M (2007) State of the union (of geometric objects): a review","DOI":"10.1090\/conm\/453\/08794"},{"key":"432_CR2","doi-asserted-by":"crossref","unstructured":"Aschner R, Katz MJ, Morgenstern G, Yuditsky Y (2013) Approximation schemes for covering and packing. In: Proceedings of the seventh international workshop on algorithms and computation, WALCOM, pp 89\u2013100","DOI":"10.1007\/978-3-642-36065-7_10"},{"key":"432_CR3","doi-asserted-by":"crossref","unstructured":"Ashok P, Kolay S, Misra N, Saurabh S (2015) Unique covering problems with geometric sets. In: Proceedings of the twenty-first international computing and combinatorics conference, COCOON, pp 548\u2013558","DOI":"10.1007\/978-3-319-21398-9_43"},{"key":"432_CR4","doi-asserted-by":"crossref","unstructured":"Bandyapadhyay S, Basu Roy A (2017) Effectiveness of local search for art gallery problems. In: Procedings of the fifteenth international symposium on algorithms and data structures, WADS, pp 49\u201360","DOI":"10.1007\/978-3-319-62127-2_5"},{"issue":"1","key":"432_CR5","first-page":"221","volume":"7","author":"N Bansal","year":"2016","unstructured":"Bansal N, Pruhs K (2016) Weighted geometric set multi-cover via quasi-uniform sampling. J Comput Geom 7(1):221\u2013236","journal-title":"J Comput Geom"},{"issue":"4","key":"432_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M Cesati","year":"1997","unstructured":"Cesati M, Trevisan L (1997) On the efficiency of polynomial time approximation schemes. Inf Process Lett 64(4):165\u2013171","journal-title":"Inf Process Lett"},{"issue":"2","key":"432_CR7","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":"1","key":"432_CR8","first-page":"9","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri C, Clarkson KL, Har-Peled S (2012) On the set multicover problem in geometric settings. ACM Trans Algorithms (TALG) 9(1):9","journal-title":"ACM Trans Algorithms (TALG)"},{"key":"432_CR9","unstructured":"Cohen-Addad V, Mathieu C (2015) Effectiveness of local search for geometric optimization. In: Proceedings of the thirty-first international symposium on computational geometry, SoCG, pp 329\u2013343"},{"key":"432_CR10","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Klein PN, Mathieu C (2016) Local search yields approximation schemes for $k$-means and $k$-median in euclidean and minor-free metrics. In: Proceedings of the IEEE fifty-seventh annual symposium on foundations of computer science, FOCS, pp 353\u2013364","DOI":"10.1109\/FOCS.2016.46"},{"issue":"2\u20133","key":"432_CR11","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.tcs.2004.02.035","volume":"320","author":"V Dahll\u00f6f","year":"2004","unstructured":"Dahll\u00f6f V, Jonsson P, Beigel R (2004) Algorithms for four variants of the exact satisfiability problem. Theor Comput Sci 320(2\u20133):373\u2013394","journal-title":"Theor Comput Sci"},{"issue":"4","key":"432_CR12","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1137\/060656048","volume":"38","author":"ED Demaine","year":"2008","unstructured":"Demaine ED, Feige U, Hajiaghayi M, Salavatipour MR (2008) Combination can be hard: approximability of the unique coverage problem. SIAM J Comput 38(4):1464\u20131483","journal-title":"SIAM J Comput"},{"key":"432_CR13","doi-asserted-by":"crossref","unstructured":"Ene A, Har-Peled S, Raichel B (2012) Geometric packing under non-uniform constraints. In: Proceedings of the twenty-eighth annual symposium on computational geometry, SoCG, pp 11\u201320","DOI":"10.1145\/2261250.2261253"},{"key":"432_CR14","unstructured":"Erlebach T, Van Leeuwen EJ (2008) Approximating geometric coverage problems. In: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA, pp 1267\u20131276"},{"issue":"3","key":"432_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler RJ, Paterson MS, Tanimoto SL (1981) Optimal packing and covering in the plane are NP-complete. Inf Process Lett 12(3):133\u2013137","journal-title":"Inf Process Lett"},{"issue":"6","key":"432_CR16","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson GN (1987) Fast algorithms for shortest paths in planar graphs, with applications. SIAM J Comput 16(6):1004\u20131022","journal-title":"SIAM J Comput"},{"key":"432_CR17","doi-asserted-by":"crossref","unstructured":"Friggstad Z, Rezapour M, Salavatipour MR (2016) Local search yields a PTAS for k-means in doubling metrics. In: Proceedings of the IEEE fifty-seventh annual symposium on foundations of computer science, FOCS, pp 365\u2013374","DOI":"10.1109\/FOCS.2016.47"},{"key":"432_CR18","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York"},{"key":"432_CR19","unstructured":"Govindarajan S, Raman R, Ray S, Basu Roy A (2016) Packing and covering with non-piercing regions. In: Procedings of the twenty-fourth annual european symposium on algorithms, ESA, pp 47:1\u201347:17"},{"key":"432_CR20","doi-asserted-by":"crossref","unstructured":"Har-Peled S (2014) Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: Proceedings of the thirtieth annual symposium on computational geometry, soCG, pp 120:120\u2013120:129","DOI":"10.1145\/2582112.2582157"},{"key":"432_CR21","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-31155-0_3","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"Takehiro Ito","year":"2012","unstructured":"Ito T, Nakano S-I, Okamoto Y, Otachi Y, Uehara R, Uno T, Uno Y (2012) A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares. In: Proceedings of the thirteenth scandinavian conference on algorithm theory, SWAT, pp 24\u201335. Springer"},{"key":"432_CR22","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, 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"},{"issue":"1","key":"432_CR23","first-page":"168","volume":"5","author":"E Krohn","year":"2014","unstructured":"Krohn E, Gibson M, Kanade G, Varadarajan K (2014) Guarding terrains via local search. J Comput Geom 5(1):168\u2013178","journal-title":"J Comput Geom"},{"key":"432_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on discrete geometry","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek J (2002) Lectures on discrete geometry. Springer, Secaucus"},{"issue":"3","key":"432_CR25","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s00453-011-9608-0","volume":"65","author":"N Misra","year":"2013","unstructured":"Misra N, Moser H, Raman V, Saurabh S, Sikdar S (2013) The parameterized complexity of unique coverage and its variants. Algorithmica 65(3):517\u2013544","journal-title":"Algorithmica"},{"issue":"4","key":"432_CR26","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa NH, Ray S (2010) Improved results on geometric hitting set problems. Discrete Comput Geom 44(4):883\u2013895","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"432_CR27","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1017\/S0963548315000280","volume":"25","author":"J Pach","year":"2016","unstructured":"Pach J, Walczak B (2016) Decomposition of multiple packings with subquadratic union complexity. Combin Probab Comput 25(1):145\u2013153","journal-title":"Combin Probab Comput"},{"key":"432_CR28","doi-asserted-by":"crossref","unstructured":"Pyrga E, Ray S (2008) New existence proofs for $\\epsilon $-nets. In: Proceedings of the twenty-fourth annual symposium on computational geometry, SoCG, pp 199\u2013207","DOI":"10.1145\/1377676.1377708"},{"key":"432_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer TJ (1978) The complexity of satisfiability problems. In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC, pp 216\u2013226","DOI":"10.1145\/800133.804350"},{"key":"432_CR30","unstructured":"Whitesides S, Zhao R (1990) K-admissible collections of Jordan curves and offsets of circular arc figures. Technical report (McGill University. School of Computer Science). McGill University, School of Computer Science"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00432-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T23:15:37Z","timestamp":1592608537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00432-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["432"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00432-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,21]]},"assertion":[{"value":"21 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}