Algebraic optimization: The Fermat-Weber location problem (Q584057)

This paper discusses some complexity and algorithmic issues concerning the well-known Fermat-Weber problem, which asks for the determination of a point minimizing the weighted sum of Euclidean distances to a given finite set of points in n-space, assumed here to have rational coordinates. First it is argued that such a solution is algebraic, and that the characteristic polynomials of the optimal value and solution coordinates may be obtained by a finite number of elementary arithmetic operations (although exactly how this is to be done efficiently is unknown), together with associated intervals in which the sought values are the unique roots. Any rootfinding method would then solve the problem, thus yielding a solution method with rate of convergence equal to that of the best one-dimensional rootfinding method for polynomials. Next it is shown how to solve the strong separation problem associated with the Fermat-Weber model. This leads, by way of an ellipsoid method to a polynomial method to construct an approximate solution of fixed accuracy.