A Cut Approach to the Rectilinear Distance Facility Location Problem

This paper is concerned with the problem of locating n new facilities in the plane when there are m facilities already located. The objective is to minimize the weighted sum of rectilinear distances. Necessary and sufficient conditions for optimality are established. We show that the optimum locations of the new facilities are dependent on the relative orderings of old facilities along the two coordinate axes but not on the distances between them. Based on these results an algorithm is presented that requires the solution of at most m − 1 minimum cut problems on networks with at most n + 2 vertices. All of these results are easily extended to the same location problem on a tree graph.