A distance constrained p-facility location problem on the real line

Let V={v1,...,vn} be a set of n points on the real line (existing facilities). The problem considered is to locate p new point facilities, F1,...,Fp, in V while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. For i=1,...,p, j=1,...,n, the cost of locating Fi at point vi is cij. The objective is to minimize the total cost of setting up the new facilities. The paper presents an 𝒪(p³n²logn) algorithm to solve the model.