  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.
