G-95-45
Dispersing Facilities on a Network
et référence BibTeX
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.
Paru en octobre 1995 , 16 pages