TY - GEN
T1 - Covering many or few points with unit disks
AU - De Berg, Mark
AU - Cabello, Sergio
AU - Har-Peled, Sariel
PY - 2007
Y1 - 2007
N2 - Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m ≥ 1, such that the total weight of the points from P inside the union of the disks is maximized. We present a deterministic algorithm that can compute, for any e > 0, a (1 - ε)-approximation to the optimal solution in O(n log n + ε-4m log2m(1/ε)) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that can compute, for any ε > 0, with high probability a (1 + ε)-approximation to the optimal solution in O(n(log 3 n + ε-4 log2 n)) expected time.
AB - Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m ≥ 1, such that the total weight of the points from P inside the union of the disks is maximized. We present a deterministic algorithm that can compute, for any e > 0, a (1 - ε)-approximation to the optimal solution in O(n log n + ε-4m log2m(1/ε)) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that can compute, for any ε > 0, with high probability a (1 + ε)-approximation to the optimal solution in O(n(log 3 n + ε-4 log2 n)) expected time.
UR - http://www.scopus.com/inward/record.url?scp=38149128164&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149128164&partnerID=8YFLogxK
U2 - 10.1007/11970125_5
DO - 10.1007/11970125_5
M3 - Conference contribution
AN - SCOPUS:38149128164
SN - 9783540695134
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 55
EP - 68
BT - Approximation and Online Algorithms - 4th International Workshop, WAOA 2006, Revised Papers
PB - Springer
T2 - 4th Workshop on Approximation and Online Algorithms, WAOA 2006
Y2 - 14 September 2006 through 15 September 2006
ER -