Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
From MaRDI portal
Publication:5419098
DOI10.1145/1993636.1993675zbMath1288.68090OpenAlexW2109237987MaRDI QIDQ5419098
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1993636.1993675
Linear programming (90C05) Markov and semi-Markov decision processes (90C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (25)
On the lexicographic centre of multiple objective optimization ⋮ Geometric random edge ⋮ More bounds on the diameters of convex polytopes ⋮ The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ The Polyhedral Geometry of Pivot Rules and Monotone Paths ⋮ Directed random walks on polytopes with few facets ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ The octatope abstract domain for verification of neural networks ⋮ A counterexample to the Hirsch conjecture ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games ⋮ Unnamed Item ⋮ Random Walks on Polytopes of Constant Corank ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Unnamed Item ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
This page was built for publication: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
