Heuristic and Special Case Algorithms for Dispersion Problems

S. S. Ravi, D. J. Rosenkrantz and G. K. Tayi
Additional contact information
S. S. Ravi: University at Albany-SUNY, Albany, New York
D. J. Rosenkrantz: University at Albany-SUNY, Albany, New York
G. K. Tayi: University at Albany-SUNY, Albany, New York

Operations Research, 1994, vol. 42, issue 2, 299-310

Abstract: The dispersion problem arises in selecting facilities to maximize some function of the distances between the facilities. The problem also arises in selecting nondominated solutions for multiobjective decision making. It is known to be NP-hard under two objectives: maximizing the minimum distance ( MAX-MIN ) between any pair of facilities and maximizing the average distance ( MAX-AVG ). We consider the question of obtaining near-optimal solutions. for MAX-MIN , 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 satisfy the triangle inequality, we analyze an efficient heuristic and show that it provides a performance guarantee of two. We also prove that obtaining a performance guarantee of less than two is NP-hard. for MAX-AVG , we analyze an efficient heuristic and show that it provides a performance guarantee of four when the distances satisfy the triangle inequality. We also present a polynomial-time algorithm for the 1-dimensional MAX-AVG dispersion problem. Using that algorithm, we obtain a heuristic which provides an asymptotic performance guarantee of π/2 for the 2-dimensional MAX-AVG dispersion problem.

Keywords: analysis of algorithms: computational complexity; facilities/equipment planning: discrete location; programming: heuristic (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.2.299 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:2:p:299-310

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().