The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
复制标题
凸多面体中的最小欧几里得范数点：沃尔夫的组合算法是指数的
DOI：
10.1137/18m1221072
复制
发表时间：
2020
影响因子：
1.6
通讯作者：
Rademacher, Luis
中科院分区：
文献类型：
--
作者：
De Loera, Jesús A.;Haddock, Jamie;Rademacher, Luis
菲利普·沃尔夫（Philip Wolfe）在1974年提出了凸多面体上最小欧氏范数点问题的方法，但该方法的复杂性一直是未知的。我们提出的第一个例子，沃尔夫的方法需要指数时间。此外，我们改进了以前的结果，证明了线性规划在强多项式时间内可归结为单纯形上的最小范数点问题
The complexity of Philip Wolfe’s method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. We present the first example that Wolfe’s method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex