Polynomial time approximation schemes for minimum disk cover problems |
| |
Authors: | Chen Liao Shiyan Hu |
| |
Institution: | 1.Department of Electrical and Computer Engineering,Michigan Technological University,Houghton,USA |
| |
Abstract: | The following planar minimum disk cover problem is considered in this paper: given a set
D\mathcal{D}
of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum
cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within
a factor of (1+ε) in
O(mnO(\frac1e2log2\frac1e))\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})})
time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover
problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several
variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem
are considered and approximation schemes are designed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|