Groupe d’études et de recherche en analyse des décisions

G-95-45

Dispersing Facilities on a Network

et

The p-maxisum dispersion problem consists of locating p facilities at vertices of a network in order to maximize the sum of the distances between all pairs of them. The decision version of this problem is shown to be strongly NP-complete. For a tree network a solution algorithm with a complexity linear in the number of vertices is proposed for fixed p. Moreover, the p-maxisum dispersion problem on a general network is shown to be a particular case of the quadratic knapsack problem, for which fairly efficient algorithms are available.

, 16 pages