Facility Dispersion Problems: Heuristics and Special Cases (Extended Abstract)

S. S. Ravi, Daniel J. Rosenkrantz, Giri Kumar TayiWADS 1991 · OpenReview

Abstract

Facility dispersion problem deals with the location of facilities on a network so as to maximize some function of the distances between facilities. We consider the problem under two different optimality criteria, namely maximizing the minimum distance (MAX-MIN) between any pair of facilities and maximizing the average distance (MAX-AVG) between any pair of facilities. Under either criterion, the problem is known to be NP-hard, even when the distances satisfy the triangle inequality. We consider the question of obtaining near-optimal solutions. For the MAX-MIN criterion, we show that if the distances do not satisfy the triangle inequality, there is no polynomial time relative approximation algorithm unless P=NP. When the distances do satisfy the triangle inequality, we present an efficient heuristic which provides a performance guarantee of 2, thus improving the performance guarantee of 3 proven in [Wh91]. We also prove that obtaining a performance guarantee of less than 2 is NP-hard. For the MAX-AVG criterion, we present a heuristic which provides a performance guarantee of 4, provided that the distances satisfy the triangle inequality. For the 1-dimensional dispersion problem, we provide polynomial time algorithms for obtaining optimal solutions under both MAX-MIN and MAX-AVG criteria. Using the latter algorithm, we obtain a heuristic which provides a performance guarantee of 4( $$\sqrt 2 - 1$$ ) ≈ 1.657 for the 2-dimensional dispersion problem under the MAX-AVG criterion.
BibTeX
@inproceedings{ravi1991facility,
  author = {S. S. Ravi and Daniel J. Rosenkrantz and Giri Kumar Tayi},
  title = {{Facility Dispersion Problems: Heuristics and Special Cases (Extended Abstract)}},
  booktitle = {WADS},
  year = {1991},
  url = {https://openreview.net/forum?id=KB7Si6Qi6Pmc},
}
Figure