TY - GEN
T1 - A 4.31-approximation for the geometric unique coverage problem on unit disks
AU - Ito, Takehiro
AU - Nakano, Shin Ichi
AU - Okamoto, Yoshio
AU - Otachi, Yota
AU - Uehara, Ryuhei
AU - Uno, Takeaki
AU - Uno, Yushi
N1 - Funding Information:
The authors thank anonymous referees of the preliminary version and of this journal version for their helpful suggestions. This work is partially supported by Grant-in-Aid for Scientific Research ( 21700009 , 22310089 , 23500005 , 23500013 , 23500022 , 24106005 , 24220003 , 24700008 , 25106504 , 25106508 , 25330003 , 25730003 ), and by the Funding Program for World-Leading Innovative R&D on Science and Technology, Japan ( JST PRESTO, Developing Algorithmic Paradigm for Similarity Structure Analysis in Large Scale Data).
PY - 2012
Y1 - 2012
N2 - 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 + ε (< 4.3095 + ε) for any fixed constant ε > 0. Our algorithm runs in polynomial time which depends exponentially on 1/ε. 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.
AB - 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 + ε (< 4.3095 + ε) for any fixed constant ε > 0. Our algorithm runs in polynomial time which depends exponentially on 1/ε. 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.
UR - http://www.scopus.com/inward/record.url?scp=84871567273&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871567273&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-35261-4_40
DO - 10.1007/978-3-642-35261-4_40
M3 - Conference contribution
AN - SCOPUS:84871567273
SN - 9783642352607
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 372
EP - 381
BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PB - Springer Verlag
T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012
Y2 - 19 December 2012 through 21 December 2012
ER -