×

An improved approximation algorithm for the most points covering problem. (English) Zbl 1253.68148

Summary: In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, \(n\) points in \(\mathbb{R}^{2}\), \(r>0\), and an integer \(m>0\) are given and the goal is to cover the maximum number of points with \(m\) disks with radius \(r\). The dual of the most points covering problem is the partial covering problem in which \(n\) points in \(\mathbb{R}^{2}\) are given, and we try to cover at least \(p\leq n\) points of these \(n\) points with the minimum number of disks. Both these problems are NP-hard. To solve the most points covering problem, we use the solution of the partial covering problem to obtain an upper bound for the problem and then we generate a valid solution for the most points covering problem by a careful modification of the partial covering solution. We first present an improved approximation algorithm for the partial covering problem which has a better running time than the previous algorithm for this problem. Using this algorithm, we attain a \((1 - \frac{{2\varepsilon }}{{1 +\varepsilon }})\)-approximation algorithm for the most points covering problem. The running time of our algorithm is \(O((1+\varepsilon)mn+\epsilon^{-1}n^{4\sqrt{2}\epsilon^{-1}+2}) \) which is polynomial with respect to both \(m\) and \(n\), whereas the previously known algorithm for this problem runs in \(O(n \log n +n\epsilon^{-6m+6} \log (\frac{1}{\epsilon}))\) which is exponential regarding \(m\).

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37, 43–58 (2007) · Zbl 1106.68121 · doi:10.1007/s00454-006-1273-8
[2] Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 3, 133–137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3
[3] Fu, B.: Theory and application of width bounded geometric separator. In: Lecture Notes in Computer Science, vol. 3884, p. 277 (2006) · Zbl 1136.68573
[4] Feige, U.: A threshold of $\(\backslash\)ln n$ for approximating set cover. J. ACM 45, 634–652 (1998) · Zbl 1065.68573 · doi:10.1145/285055.285059
[5] Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985) · Zbl 0633.68027 · doi:10.1145/2455.214106
[6] Gonzalez, T.F.: Covering a set of points in multidimensional space. Inf. Process. Lett. 40, 181–188 (1991) · Zbl 0748.68083 · doi:10.1016/0020-0190(91)90075-S
[7] Fu, B., Chen, Z., Abdelguerfi, M.: An almost linear time 2.8334-approximation algorithm for the disc covering problem. In: Lecture Notes on Computer Science, vol. 4508, pp. 317–329 (2007) · Zbl 1137.68610
[8] Cook, M.F.M., Franceschetti, M., Bruck, J.: A geometric theorem for network design. IEEE Trans. Comput. 53, 483–489 (2004) · doi:10.1109/TC.2004.1268406
[9] Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53, 55–84 (2004) · Zbl 1068.68177 · doi:10.1016/j.jalgor.2004.04.002
[10] Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70, 39–45 (1999) · Zbl 1002.68203 · doi:10.1016/S0020-0190(99)00031-9
[11] Chazelle, B.M., Lee, D.T.: On a circle placement problem. Computing 36, 1–16 (1986) · Zbl 0572.65051 · doi:10.1007/BF02238188
[12] Berg, M.D., Cabello, S., Har-Peled, S.: Covering many or few points with unit disks. Theory Comput. Syst. 45, 446–469 (2009) · Zbl 1187.68716 · doi:10.1007/s00224-008-9135-9
[13] Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33, 201–226 (2002) · Zbl 0994.68178 · doi:10.1007/s00453-001-0110-y
[14] Cormen, T.H., Leiserson, C.E., Rivest, R.I., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001) · Zbl 1047.68161
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.