On Simplex Pivoting Rules and Complexity Theory
On Simplex Pivoting Rules and Complexity Theory
复制标题
论单纯形枢轴规则和复杂性理论
DOI：
10.1007/978-3-319-07557-0_2
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Rubinstein
中科院分区：
文献类型：
--
作者：
I. Adler;C. Papadimitriou;A. Rubinstein
我们表明，有一些简单的规则是pspace-complete，以确定特定基础是否会出现在算法的路径上。可以显示单纯形方法的大多数变体。
We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm’s path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig’s shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.