ALGEBRAIC OPTIMIZATION - THE FERMAT-WEBER LOCATION PROBLEM
ALGEBRAIC OPTIMIZATION - THE FERMAT-WEBER LOCATION PROBLEM
复制标题
DOI：
10.1007/bf01585739
复制
发表时间：
1990-02-01
影响因子：
2.7
通讯作者：
TAMIR, A
中科院分区：
文献类型：
--
作者：
CHANDRASEKARAN, R;TAMIR, A
费马-韦伯选址问题是在ℝn中寻找一个点，使ℝn中给定点之间的(加权)欧氏距离之和最小。本文讨论了一些相关的复杂性和算法问题。首先，利用Tarski关于实闭域上的可解性的理论，我们证明了存在一个无穷大的格式来解决这个问题，其中收敛速度等于寻找一维多项式的实代数根的最佳方法的速度。其次，我们给出了与Fermat-Weber模型相关的强分离问题的显式解。这一分离结果表明，用标准椭球方法可以在多项式时间内构造出ε逼近解。
The Fermat-Weber location problem is to find a point in ℝnthat minimizes the sum of the (weighted) Euclidean distances frommgiven 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.