Paper Info
Title
A 4.31-approximation for the geometric unique coverage problem on unit disks
Abstract
We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2+4/3+@e(0. Our algorithm runs in polynomial time which depends exponentially on 1/@e. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.
Year
DOI
Venue
2012
10.1016/j.tcs.2014.04.014
Theoretical Computer Science
Keywords
DocType
Volume
approximation algorithm,computational geometry,unique coverage problem,unit disk
Conference
544,
ISSN
Citations 
PageRank 
0304-3975
2
0.39
References 
Authors
8
7
Name
Order
Citations
PageRank
Takehiro Ito126040.71
Shin-ichi Nakano224624.40
Yoshio Okamoto317028.50
Yota Otachi416137.16
Ryuhei Uehara552875.38
Takeaki Uno61319107.99
yushi uno722228.80