Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

ABSTRACT

Let D be a set of disks of arbitrary radii in the plane, and let P be a set of points. We study the following three problems: (i) Assuming P contains the set of center points of disks in D, find a minimum-cardinality subset P^* of P (if exists), such that each disk in D is pierced by at least h points of P^*, where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming P is such that for each D@?D there exists a point in P whose distance from D's center is at most @ar(D), where r(D) is D's radius and 0=<@a<1 is a given constant, find a minimum-cardinality subset P^* of P, such that each disk in D is pierced by at least one point of P^*. We call this problem minimum discrete piercing with cores. (iii) Assuming P is the set of center points of disks in D, and that each D@?D covers at most l points of P, where l is a constant, find a minimum-cardinality subset D^* of D, such that each point of P is covered by at least one disk of D^*. We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178-189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+@e)-approximation for minimum discrete piercing (i.e., for arbitrary P).

REFERENCES

• [1]: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• [2]: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• [3]: Brönnimann, H. and Goodrich, M.T., Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. v14. 463-479.
• [4]: Gruia Călinescu , Ion I. Mandoiu , Peng-Jun Wan , Alexander Z. Zelikovsky, Selecting forwarding neighbors in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.101-111, April 2004 [doi>10.1023/B:MONE.0000013622.63511.57]
• [5]: 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]
• [6]: 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]
• [7]: Kenneth L. Clarkson , Kasturi Varadarajan, Improved approximation algorithms for geometric set cover, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064115]
• [8]: Alon Efrat , Matthew J. Katz , Frank Nielsen , Micha Sharir, Dynamic data structures for fat objects and their applications, Computational Geometry: Theory and Applications, v.15 n.4, p.215-227, April 2000 [doi>10.1016/S0925-7721(99)00059-0]
• [9]: T. Erlebach, Personal communication, 2006
• [10]: 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]
• [11]: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• [12]: David S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, v.13 n.3, p.502-524, Sept. 1992 [doi>10.1016/0196-6774(92)90052-E]
• [13]: Nissan Lev-Tov , David Peleg, Polynomial time approximation schemes for base station coverage with minimum total radii, Computer Networks and ISDN Systems, v.47 n.4, p.489-501, 15 March 2005 [doi>10.1016/j.comnet.2004.08.012]
• [14].: Simple heuristics for unit disk graphs. Networks. v25. 59-68.
• [15]: S. Narayanappa, P. Vojtěchovský, An improved approximation factor for the unit disk covering problem, in: Proc. 18th Canadian Conf. on Comput. Geom., 2006, pp. 15--18
• [16]: T. Nieberg, J.L. Hurink, A PTAS for the minimum dominating set problem in unit disk graphs, in: Proc. 3rd Workshop on Approximation and Online Algorithms, 2005, pp. 296--306
• [17]: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• [18]: W. D. Smith , N. C. Wormald, Geometric Separator Theorems and Applications, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.232, November 08-11, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Theory

Keywords:
Approximation algorithms, Covering, Discrete piercing, Geometric optimization, Wireless networks