Algebraic properties of location problems with one circular barrier. (Q1420408)

A single location problem in the plane is considered where the location of the new facility as well as transportation is subject to a circular barrier. This means that the new location cannot be placed inside the circle and the paths between existing locations and the (unknown) new location must not travers the circle. As a consequence, the problem of minimizing the sum of the barrier distances is a non-convex optimization problem. The author shows that this problem is separable into a polynomial number of convex optimization problems. This is achieved by a tesselation of the plane into so-called cells of algebraic invariance (CAI), the latter depending on the existing facilities and the location and size of the circular barrier. It is shown that only a polynomial number of CAIs is needed, thus yielding a polynomial solution algorithm (including the solution of a convex optimization problem as black box in each iteration). The paper also includes a faster heuristic for the barrier problem.