Polynomial time approximation schemes for minimum disk cover problems

ISSN： 1382-6905

Source： Journal of Combinatorial Optimization, Vol.20, Iss.4, 2010-11, pp. : 399-412

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The following planar minimum disk cover problem is considered in this paper: given a set $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 $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.