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 algorithms that compute, for any fixed ε > 0, a (1 - ε)-approximation to the optimal solution in O(nlog n) 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 computes, for any fixed ε > 0, in O(nlog 2n) expected time a disk that is, with high probability, a (1 + ε)- approximation to the optimal solution.
Original language | English (US) |
---|---|
Pages (from-to) | 446-469 |
Number of pages | 24 |
Journal | Theory of Computing Systems |
Volume | 45 |
Issue number | 3 |
DOIs | |
State | Published - Jul 2009 |
Keywords
- Facility location
- Geometric optimization
- Random sample
- Weighted points
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics