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 the authors discuss some relevant complexity and algorithmic issues. First, using Tarski’s theory on solvability over real closed fields they 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, the authors 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.
