We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An Improved Approximation Algorithm for the Most Points Covering Problem.
- Authors
Ghasemalizadeh, Hossein; Razzazi, Mohammadreza
- Abstract
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 R, 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 R are given, and we try to cover at least p≤ 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.
- Subjects
APPROXIMATION algorithms; POLYNOMIALS; PROBLEM solving; COMPUTATIONAL geometry; COMPUTATIONAL complexity; NUMBER theory
- Publication
Theory of Computing Systems, 2012, Vol 50, Issue 3, p545
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-011-9353-4