The Simplex Algorithm Is NP-Mighty

DOI10.1145/3280847zbMath1454.90024arXiv1311.5935WikidataQ60358029 ScholiaQ60358029MaRDI QIDQ4629975

Yann Disser, Martin Skutella

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.5935

zbMATH Keywords

simplex algorithm; network simplex; earliest arrival flows; successive shortest paths; NP-mightiness

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C05: Linear programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

90C49: Extreme-point and pivoting methods