A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.