A BSSS algorithm for the single facility location problem in two regions with different norms

Abstract

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a<br><br>single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a<br><br>non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides<br><br>of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the<br><br>optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small<br><br>square (BSSS) procedure is proposed.