Approximation algorithms for dispersion problems

Dispersion problems involve arranging a set of points as far away from each other as possible. They have numerous applications in the location of faci lities and in management decision science. We suggest a simple formalism th at lets us describe different dispersal problems in a uniform way. We prese nt several algorithms and hardness results for dispersion problems using di fferent natural measures of remoteness, some of which have been studied pre viously in the literature and others that we introduce; in particular, we g ive the first algorithm with a nontrivial performance guarantee for the pro blem of locating a set of points such that the sum of their distances to th eir nearest neighbor in the set is maximized. (C) 2001 Academic Press.