A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games

DOI10.1007/978-3-642-20807-2_16zbMath1341.90143OpenAlexW186942940MaRDI QIDQ3009763

Oliver Friedmann

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_16

Mathematics Subject Classification ID

Linear programming (90C05) Applications of game theory (91A80) Markov and semi-Markov decision processes (90C40) Extreme-point and pivoting methods (90C49)

Related Items (21)

Geometric random edge ⋮ Symmetric Strategy Improvement ⋮ 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 ⋮ Abstract tropical linear programming ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ A counterexample to the Hirsch conjecture ⋮ Unnamed Item ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ A double-pivot simplex algorithm and its upper bounds of the iteration numbers ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ An exponential lower bound for Cunningham's rule ⋮ On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes ⋮ 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 ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The worst-case running time of the random simplex algorithm is exponential in the height
• Worst case behavior of the steepest edge simplex method
• Randomized simplex algorithms on Klee-Minty cubes
• Linear programming, the simplex algorithm and simple polytopes
• Balanced Gray codes
• Automata, logics, and infinite games. A guide to current research
• A subexponential bound for linear programming
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Finite state Markovian decision processes
• Exponential Lower Bounds for Policy Iteration
• Affirmative action algorithms
• One line and n points
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

This page was built for publication: A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games