@inproceedings{4f4ef6ffc7c54f739c7065925e50242c,

title = "Covering many or few points with unit disks",

abstract = "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-e)-approximation to the optimal solution in O(n logn + e-4mlog2m (1/e)) 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 e>0, with high probability a (1+e)-approximation to the optimal solution in O(n (log3 n + e-4 log2 n )) expected time.",

author = "{Berg, de}, M. and S. Cabello and S. Har-Peled",

year = "2007",

doi = "10.1007/11970125_5",

language = "English",

isbn = "978-3-540-69513-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "55--68",

editor = "T. Erlebach and C. Kaklamanis",

booktitle = "Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA 2006) 14-15 September 2006, Z{\"u}rich, Switzerland",

address = "Germany",

note = "conference; WAOA 2006, Zurich, Switzerland; 2006-09-14; 2006-09-15 ; Conference date: 14-09-2006 Through 15-09-2006",

}