The Simplex Algorithm Is NP-Mighty
ACM Transactions on Algorithms · 31.01.2019 · 15 (1) · 1-19
DOI: 10.1145/3280847 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 16.11.2018. Verfasst von Yann Disser und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: Alexander von Humboldt-Foundation, DFG Priority Programme 1736 “Algorithms for Big Data”.
Abstract (Originalsprache)
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.
Förderung
- Alexander von Humboldt-Foundation
- DFG Priority Programme 1736 “Algorithms for Big Data”
Zitieren
APA
Disser, Y., & Skutella, M. (2019). The Simplex Algorithm Is NP-Mighty. ACM Transactions on Algorithms, 15(1), 1-19. https://doi.org/10.1145/3280847
Vancouver
Disser Y, Skutella M. The Simplex Algorithm Is NP-Mighty. ACM Transactions on Algorithms. 2019;15(1):1-19. doi:10.1145/3280847
BibTeX
@article{Disser2019,
author = {Disser, Yann and Skutella, Martin},
title = {The Simplex Algorithm Is NP-Mighty},
journal = {ACM Transactions on Algorithms},
year = {2019},
volume = {15},
number = {1},
pages = {1--19},
doi = {10.1145/3280847}
}
EUVIMED