ALGEBRAIC OPTIMIZATION: THE FERMAT -- WEBER LOCATION PROBLEM

	The Fermat-Weber location problem is to find a point in R**n that minimizes the
sum of the (weighted) Euclidean distances from m given points in R**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 epsilon approximation solution can be 
constructed in polynomial time using the standard Ellipsoid Method. Finally, focusing 
on the popular iterative solution method due to Weiszfeld, we point out a flaw in 
Kuhn's main convergence result about this method.