2015 | OriginalPaper | Chapter
A PTAS for the Weighted Unit Disk Cover Problem
Authors : Jian Li, Yifei Jin
Published in: Automata, Languages, and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We are given a set of weighted unit disks and a set of points in Euclidean plane. The minimum weight unit disk cover (
WUDC
) problem asks for a subset of disks of minimum total weight that covers all given points.
WUDC
is one of the geometric set cover problems, which have been studied extensively for the past two decades (for many different geometric range spaces, such as (unit) disks, halfspaces, rectangles, triangles). It is known that the unweighted
WUDC
problem is NP-hard and admits a polynomial-time approximation scheme (PTAS). For the weighted
WUDC
problem, several constant approximations have been developed. However, whether the problem admits a PTAS has been an open question. In this paper, we answer this question affirmatively by presenting the first PTAS for
WUDC
. Our result implies the first PTAS for the minimum weight dominating set problem in unit disk graphs. Combining with existing ideas, our result can also be used to obtain the first PTAS for the maxmimum lifetime coverage problem and an improved constant approximation ratio for the connected dominating set problem in unit disk graphs.