Approximating geometric coverage problems

ABSTRACT

We present the first study on the approximability of geometric versions of the unique coverage problem and the minimum membership set cover problem. In the former problem, one is given a family of sets of elements from some universe and aims to select sets that maximize the number of elements contained in precisely one selected set. Unique Coverage has important applications in wireless networks and it is thus natural to consider it in a geometric setting. We use the well-known (unit) disk model for wireless networks and show that Unique Coverage remains NP-hard in this case and present a polynomial-time 1/18-approximation algorithm. This algorithm is extended to the budgeted low-coverage problem, where covering can element multiple times yields less profit and we have a fixed budget to 'buy' sets. We give an asymptotic FPTAS in case the disks have arbitrary size, but bounded ply. For the case that the geometric objects are arbitrary fat objects, we show that these problems are as hard to approximate as in the general case. In the minimum membership set cover problem, the goal is to cover all elements while minimizing the maximum number of sets in which any element is contained. For unit squares and unit disks, we show that the problem remains NP-hard and does not admit a polynomial-time approximation algorithm with ratio smaller than 2 unless P=NP. For unit squares, we give a 5-approximation algorithm for instances where the optimum objective value is bounded by a constant.

REFERENCES

• 1: Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M., "Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs" in Proc. APPROX-RANDOM 2006, LNCS 4110, Springer-Verlag, Berlin, 2006, pp. 3--14.
• 2: Brönnimann, H., Goodrich, M. T., "Almost Optimal Set Covers in Finite VC-Dimension", Discrete Comput. Geom. 14 4 (1995), pp. 463--479.
• 3: Carmi, P., Katz, M. J., Lev-Tov, N., "Covering Points by Unit Disks of Fixed Location" in Proc. ISAAC 2007, LNCS, Springer, 2007. To appear.
• 4: Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003 [doi>10.1016/S0196-6774(02)00294-8]
• 5: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O ]
• 6: Kenneth L. Clarkson , Kasturi Varadarajan, Improved Approximation Algorithms for Geometric Set Cover, Discrete & Computational Geometry, v.37 n.1, p.43-58, January 2007 [doi>10.1007/s00454-006-1273-8]
• 7: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109577]
• 8: Efrat, A., Sharir, M., "The Complexity of the Union of Fat Objects in the Plane", Discrete Comput. Geom. 23 2 (Feb. 2000), pp. 171--189.
• 9: Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, SIAM Journal on Computing, v.34 n.6, p.1302-1323, 2005 [doi>10.1137/S0097539702402676]
• 10: Erlebach, T., van Leeuwen, E. J., "Domination in Geometric Intersection Graphs", Manuscript, 2007
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Christian Glaßer , Steffen Reith , Heribert Vollmer, The complexity of base station positioning in cellular networks, Discrete Applied Mathematics, v.148 n.1, p.1-12, 30 April 2005 [doi>10.1016/j.dam.2004.07.005]
• 13: Guruswami, V., Trevisan, L., "The Complexity of Making Unique Choices: Approximating 1-in-k SAT" in Proc. APPROX-RANDOM 2005, LNCS 3624, Springer-Verlag, Berlin, 2005, pp. 99--110.
• 14: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 15: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9 ]
• 16: Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A., "Interference in Cellular Networks: The Minimum Membership Set Cover Problem" in Proc. COCOON 2005, LNCS 3595, Springer-Verlag, Berlin, 2005, pp. 188--198.
• 17: Nissan Lev-Tov , David Peleg, Exact Algorithms and Approximation Schemes for Base Station Placement Problems, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.90-99, July 03-05, 2002
• 18: Moser, H., Raman, V., Sikdar, S., "The Parameterized Complexity of the Unique Coverage Problem" in Proc. ISAAC 2007, LNCS, Springer, 2007. To appear.
• 19: van Leeuwen, E. J., "Better Approximation Schemes for Disk Graphs" in Proc. SWAT 2006, LNCS 4059, Springer-Verlag, Berlin, 2006, pp. 316--327.