Heuristic and special case algorithms for dispersion problems

Heuristic and special case algorithms for dispersion problems

0.00 Avg rating0 Votes
Article ID: iaor1995263
Country: United States
Volume: 42
Issue: 2
Start Page Number: 299
End Page Number: 310
Publication Date: Mar 1994
Journal: Operations Research
Authors: , ,
Keywords: facilities, location, heuristics
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). The authors consider the question of obtaining near-optimal solutions. For MAX-MIN, they 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, the authors analyze an efficient heuristic and show that it provides a performance guarantee of two. They also prove that obtaining a performance guarantee is less than two is NP-hard. For MAX-AVG, the authors analyze an efficient heuristic and show that it provides a performance guarantee of four when the distances satisfy the triangle inequality. They also present a polynomial-time algorithm for the 1-dimensional MAX-AVG dispersion problem. Using that algorithm, the authors obtain a heuristic which provides an asymptotic performance guarantee of ;/2 for the 2-dimensional MAX-AVG dispersion problem.

Reviews

Required fields are marked *. Your email address will not be published.