The Simplex Algorithm Is NP-Mighty
The Simplex Algorithm Is NP-Mighty
复制标题
单纯形算法具有 NP 强大性
DOI：
10.1145/3280847
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Martin
中科院分区：
文献类型：
--
作者：
Disser;Skutella;Martin
我们证明了单纯形法、网络单纯形法（均采用Dantzig的原始主元规则）和逐次最短路算法都是NP-强大的。也就是说，这些算法中的每一个都可以用于在算法执行期间隐式地解决NP中的任何问题。这一结果对这些算法的指数最坏情况运行时间投下了更有利的光。此外，作为我们的方法的结果，我们得到了一些新的硬度结果。例如，对于单纯形算法的给定输入，决定给定变量是否在算法执行期间进入基础并确定所需的迭代次数都是NP难问题。最后，我们关闭了一个长期存在的开放问题，在该地区的网络流量随着时间的推移，最早到达的流量是NP难获得。
We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm areNP-mighty. That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This result casts a more favorable light on these algorithms’ exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm’s execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.
登录
查看更多内容
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
论本地搜索的复杂性
DOI：
--
发表时间：
1990
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
C. Papadimitriou;A. Schäffer;M. Yannakakis
通讯作者：
M. Yannakakis
变形产品和多面体的最大阴影
DOI：
10.1090/conm/223/03132
发表时间：
1996
期刊：
Journal of The Society for Industrial and Applied Mathematics
影响因子：
--
作者：
N. Amenta;G. Ziegler
通讯作者：
G. Ziegler
论单纯形法的复杂性
DOI：
--
发表时间：
1994
期刊：
影响因子：
--
作者：
D. Goldfarb
通讯作者：
D. Goldfarb
全交换机策略改进的复杂性
DOI：
10.23638/lmcs-14(4:9)2018
发表时间：
2015
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
John Fearnley;Rahul Savani
通讯作者：
Rahul Savani