An Improved Approximation Algorithm for the Most Points Covering Problem
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-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 R-2 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 - 2 epsilon/1+)-approximation algorithm for the most points covering problem. The running time of our algorithm is O((1 + epsilon) mn + epsilon(-1)n(4)root 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(1/epsilon)) which is exponential regarding m.
approximation algorithm most points covering partial covering geometric covering computational geometry