The Simplex Algorithm Is NP-Mighty

作     者：Disser, Yann Skutella, Martin 

作者机构：Tech Univ Darmstadt Dept Math Dolivostr 15 D-64293 Darmstadt Germany TU Berlin Inst Math Str 17 Juni 136 D-10623 Berlin Germany 

出 版 物：《ACM TRANSACTIONS ON ALGORITHMS》 (ACM Trans. Algorithms)

年 卷 期：2019年第15卷第1期

页      面：1–19页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：DFG Priority Programme 1736 "Algorithms for Big Data" [SK 58/10-2] Alexander von Humboldt-Foundation 

主　　题：Simplex algorithm network simplex successive shortest paths NP-mightiness earliest arrival flows 

摘      要：We show that the Simplex Method, the Network Simplex Method-both with Dantzig s original pivot rule- and the Successive Shortest Path Algorithm are NP-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.