An Improved Approximation Algorithm for the Most Points Covering Problem |
| |
Authors: | Email author" target="_blank">Hossein?GhasemalizadehEmail author Mohammadreza?Razzazi |
| |
Affiliation: | 1.SSRD lab, Department of Computer Engineering and Information Technology,Amirkabir University of Technology,Tehran,Iran;2.School of Computer Science,Institute for Research in Fundamental Sciences (IPM),Tehran,Iran |
| |
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 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 - \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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|