A multimedian problem with interdistance constraints

The location of n new facilities on a network when the objective function is a sum of weighted distances between new and existing facilities, plus a sum of weighted distances between new facilities is studied. Interdistance constraints which impose upper bounds on distances between facilities have been included. A linear programming approach has been developed which solves the problem exactly on any spanning tree of the network, and which yields a lower bounding problem when the network is cyclic. The gap between the best spanning tree solution and the lower bound averages about 4% in the computational studies.