The Simplex Algorithm Is NP-Mighty
From MaRDI portal
Publication:4629975
DOI10.1145/3280847zbMath1454.90024arXiv1311.5935WikidataQ60358029 ScholiaQ60358029MaRDI QIDQ4629975
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
simplex algorithm; network simplex; earliest arrival flows; successive shortest paths; NP-mightiness
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