On the Complexity of the Simplex Method
On the Complexity of the Simplex Method
复制标题
论单纯形法的复杂性
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
D. Goldfarb
中科院分区：
文献类型：
--
作者：
D. Goldfarb
尽管实践中的单纯形方法的效率已经充分记录在实践中，但该方法的理论复杂性仍然尚未完全理解。在本文中，我们简要回顾了有关通用线性程序和网络流问题的简单方法的最差案例复杂性以及基于概率分析的某些变体的预期行为的了解。我们还提供了一个新的证明，证明了一个事实，即众所周知，在解决问题的问题上，该算法具有预期的复杂性，在解决问题的方面是多项式的，在最坏情况下会执行指数数的枢轴数量。
Although the efficiency of the simplex method in practice is well documented, the theoretical complexity of the method is still not fully understood. In this paper we briefly review what is known about the worst-case complexity of variants of the simplex method for both general linear programs and network flow problems and the expected behavior of some of these variants based upon probabilistic analysis. We also give a new proof of the fact that the parametric-objective simplex algorithm, which is known to have an expected complexity that is polynomial in the dimensions of the problems being solved, performs an exponential number of pivots in the worst case.