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 (11)

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

This page was built for publication: The Simplex Algorithm Is NP-Mighty