Abstract:
Facility dispersion problems deal with the location of facilities on a network so as to maximize some function of the distances between facilities. These problems model situations in which proximity of facilities is undesireable. The problem has been studied in the literature 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, it is easy to see that the problem is NP-hard, even when the distances satisfy the triangle inequality. Motivated by the practical importance of these problems, we address the question of obtaining near-optimal solutions for them. We will consider both geometric and general versions of these problems. the main part of the talk will be an exposition of known results concerning the approximability of the problems. We will also present some recent results for some variations of dispersion problems.

This research was carried out jointly with Professors Daniel J. Rosenkrantz (Computer Science Department, University at Albany - SUNY) and Giri K. Tayi (School of Business, University at Albany - SUNY).

Interessenten sind herzlich eingeladen.

[Institut] [Lehrstuhl I] [Mitarbeiter] [Vorlesungen] [Veröffentlichungen]

Letzte Änderung: 18.10.2000
Bei Problemen: webmaster@optix.informatik.uni-wuerzburg.de