Computer Science – Data Structures and Algorithms
Scientific paper
2003-10-17
Algorithmica, 38 (3) 2004, 501-511.
Computer Science
Data Structures and Algorithms
13 pages, 1 figure, Latex, to appear in Algorithmica
Scientific paper
We consider a facility location problem, where the objective is to ``disperse'' a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.
Fekete Sandor P.
Meijer Henk
No associations
LandOfFree
Maximum dispersion and geometric maximum weight cliques does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum dispersion and geometric maximum weight cliques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum dispersion and geometric maximum weight cliques will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-439778