×

Local search strikes again: PTAS for variants of geometric covering and packing. (English) Zbl 1434.68597

Summary: Geometric Covering and Packing problems have been extensively studied in the last few decades and have applications in diverse areas. Several variants and generalizations of these problems have been studied recently. In this paper, we look at the following covering variants where we require that each point is “uniquely” covered, i.e., it is covered by exactly one object: Unique Coverage problem, where we want to maximize the number of uniquely covered points and Exact Cover problem, where we want to uniquely cover every point and minimize the number of objects used for covering. We also look at the following generalizations: Multi Cover problem, a generalization of Set Cover, the objective is to select the minimum subset of objects with the constraint that each input point \(p\) is covered by at least \(d_p\) objects in the solution, where \(d_p\) is the demand of point \(p\). And Shallow Packing problem, a generalization of Packing problem, where we want to select the maximum subset of objects with the constraint that any point in the plane is contained in at most \(k\) objects in the solution. The above problems are NP-hard even for unit squares in the plane. Thus, the focus has been on obtaining good approximation algorithms. Local search has been quite successful in the recent past in obtaining good approximation algorithms for a wide variety of problems. We consider the Unique Coverage and Multi Cover problems on non-piercing objects, which is a broad class that includes squares, disks, pseudo-disks, etc. and show that the local search algorithm yields a PTAS approximation under the assumption that the depth of every input point is at most some fixed constant. For Unique Coverage we further assume that every object has at most a constant degree. For the Shallow Packing problem, we show that the local search algorithm yields a PTAS approximation for objects with sub-quadratic union complexity, which is a very broad class of objects that even includes non-piercing objects. For the Exact Cover problem, we show that finding a feasible solution is NP-hard even for unit squares in the plane, thus negating the existence of polynomial time approximation algorithms.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
Full Text: DOI

References:

[1] Agarwal PK, Pach J, Sharir M (2007) State of the union (of geometric objects): a review · Zbl 1155.52017
[2] 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-100 · Zbl 1379.68344
[3] 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-558 · Zbl 1391.68103
[4] 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-60 · Zbl 1491.68254
[5] Bansal, N.; Pruhs, K., Weighted geometric set multi-cover via quasi-uniform sampling, J Comput Geom, 7, 1, 221-236 (2016) · Zbl 1405.68396
[6] Cesati, M.; Trevisan, L., On the efficiency of polynomial time approximation schemes, Inf Process Lett, 64, 4, 165-171 (1997) · Zbl 1337.68125 · doi:10.1016/S0020-0190(97)00164-6
[7] Chan, Tm; Har-Peled, S., Approximation algorithms for maximum independent set of pseudo-disks, Discrete Comput Geom, 48, 2, 373-392 (2012) · Zbl 1248.05135 · doi:10.1007/s00454-012-9417-5
[8] Chekuri, C.; Clarkson, Kl; Har-Peled, S., On the set multicover problem in geometric settings, ACM Trans Algorithms (TALG), 9, 1, 9 (2012) · Zbl 1301.68237
[9] 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-343 · Zbl 1378.68167
[10] 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-364 · Zbl 1421.68205
[11] Dahllöf, V.; Jonsson, P.; Beigel, R., Algorithms for four variants of the exact satisfiability problem, Theor Comput Sci, 320, 2-3, 373-394 (2004) · Zbl 1068.68068 · doi:10.1016/j.tcs.2004.02.035
[12] Demaine, Ed; Feige, U.; Hajiaghayi, M.; Salavatipour, Mr, Combination can be hard: approximability of the unique coverage problem, SIAM J Comput, 38, 4, 1464-1483 (2008) · Zbl 1192.68353 · doi:10.1137/060656048
[13] 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-20 · Zbl 1293.05243
[14] 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-1276 · Zbl 1192.68743
[15] Fowler, Rj; Paterson, Ms; Tanimoto, Sl, Optimal packing and covering in the plane are NP-complete, Inf Process Lett, 12, 3, 133-137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3
[16] Frederickson, Gn, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J Comput, 16, 6, 1004-1022 (1987) · Zbl 0654.68087 · doi:10.1137/0216064
[17] 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-374 · Zbl 1422.68296
[18] Garey, Mr; Johnson, Ds, Computers and intractability: a guide to the theory of NP-completeness (1979), New York: W. H. Freeman & Co., New York · Zbl 0411.68039
[19] 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-47:17 · Zbl 1397.68225
[20] 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-120:129 · Zbl 1395.68306
[21] Ito, Takehiro; Nakano, Shin-Ichi; Okamoto, Yoshio; Otachi, Yota; Uehara, Ryuhei; Uno, Takeaki; Uno, Yushi, A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares, Algorithm Theory - SWAT 2012, 24-35 (2012), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1357.68293
[22] Ito, T.; Nakano, S.; Okamoto, Y.; Otachi, Y.; Uehara, R.; Uno, T.; Uno, Y., A 4.31-approximation for the geometric unique coverage problem on unit disks, Theor Comput Sci, 544, 14-31 (2014) · Zbl 1357.68294 · doi:10.1016/j.tcs.2014.04.014
[23] Krohn, E.; Gibson, M.; Kanade, G.; Varadarajan, K., Guarding terrains via local search, J Comput Geom, 5, 1, 168-178 (2014) · Zbl 1404.68195
[24] Matoušek, J., Lectures on discrete geometry (2002), Secaucus: Springer, Secaucus · Zbl 0999.52006
[25] Misra, N.; Moser, H.; Raman, V.; Saurabh, S.; Sikdar, S., The parameterized complexity of unique coverage and its variants, Algorithmica, 65, 3, 517-544 (2013) · Zbl 1290.68059 · doi:10.1007/s00453-011-9608-0
[26] Mustafa, Nh; Ray, S., Improved results on geometric hitting set problems, Discrete Comput Geom, 44, 4, 883-895 (2010) · Zbl 1207.68420 · doi:10.1007/s00454-010-9285-9
[27] Pach, J.; Walczak, B., Decomposition of multiple packings with subquadratic union complexity, Combin Probab Comput, 25, 1, 145-153 (2016) · Zbl 1371.52017 · doi:10.1017/S0963548315000280
[28] 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-207 · Zbl 1221.52016
[29] Schaefer TJ (1978) The complexity of satisfiability problems. In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC, pp 216-226 · Zbl 1282.68143
[30] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.