{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:26:54Z","timestamp":1760441214934},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n<jats:sup>8<\/jats:sup> log n) and O(n<jats:sup>15<\/jats:sup> log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio [Formula: see text] in n<jats:sup>O(k)<\/jats:sup> time. <\/jats:p>","DOI":"10.1142\/s021819591350009x","type":"journal-article","created":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T02:29:37Z","timestamp":1405391377000},"page":"461-477","source":"Crossref","is-referenced-by-count":13,"title":["APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS"],"prefix":"10.1142","volume":"23","author":[{"given":"MINATI","family":"DE","sequence":"first","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GAUTAM K.","family":"DAS","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati - 781039, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAZ","family":"CARMI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva - 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SUBHAS C.","family":"NANDY","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,7,14]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90105-X"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1023\/B:MONE.0000013622.63511.57"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.01.001"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0295-7_15"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2004.06.012"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9417-5"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"issue":"1","key":"p_15","first-page":"77","volume":"2","author":"Claude F.","year":"2010","journal-title":"Discr. Math. Alg. Appl."},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.11.015"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912500094"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-011-1026-1"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90075-S"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-008-9146-0"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9285-9"},{"key":"p_36","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.022"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591350009X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T14:28:37Z","timestamp":1565188117000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591350009X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":20,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2014,7,14]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S021819591350009X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591350009x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}