ALGEBRAIC OPTIMIZATION - THE FERMAT-WEBER LOCATION PROBLEM

The Fermat-Weber location problem is to find a point in ℝn that minimizes the sum of the (weighted) Euclidean distances from m given points in ℝn. In this work we discuss some relevant complexity and algorithmic issues. First, using Tarski's theory on solvability over real closed fields we argue that there is an infinite scheme to solve the problem, where the rate of convergence is equal to the rate of the best method to locate a real algebraic root of a one-dimensional polynomial. Secondly, we exhibit an explicit solution to the strong separation problem associated with the Fermat-Weber model. This separation result shows that an ε-approximation solution can be constructed in polynomial time using the standard Ellipsoid Method. © 1990 North-Holland.