Algebraic optimization: The Fermat-Weber location problem |
| |
Authors: | R Chandrasekaran A Tamir |
| |
Institution: | (1) University of Texas, Dallas, TX, USA;(2) New York University, NY, USA;(3) Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | The Fermat-Weber location problem is to find a point in
n
that minimizes the sum of the (weighted) Euclidean distances fromm 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. |
| |
Keywords: | Algebraic optimization location theory ellipsoid algorithms |
本文献已被 SpringerLink 等数据库收录! |
|