The Simplex Algorithm Is NP-Mighty

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

Martin Skutella, Yann Disser

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 algorithmnetwork simplexearliest arrival flowssuccessive shortest pathsNP-mightiness

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Extreme-point and pivoting methods (90C49)

Related Items

Macroscopic evacuation plans for natural disasters. A lexicographical approach for duration and safety criteria: \(\mathrm{Lex}((Q|S)\mathrm{Flow})\), Algorithms for Flows over Time with Scheduling Costs, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, An exponential lower bound for Zadeh's pivot rule, Dynamic flows with time-dependent capacities, Lexicographically optimal earliest arrival flows, The Polyhedral Geometry of Pivot Rules and Monotone Paths, Inapproximability of shortest paths on perfect matching polytopes, Unnamed Item, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, Algorithms for flows over time with scheduling costs