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 -