An exponential lower bound for Zadeh's pivot rule

DOI10.1007/s10107-022-01848-xarXiv1911.01074OpenAlexW2985441210WikidataQ114228488 ScholiaQ114228488MaRDI QIDQ6038661

Alexander V. Hopp, Yann Disser, Oliver Friedmann

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.01074

zbMATH Keywords

Markov decision processesparity gameslower boundsimplex methodpolicy iterationstrategy improvementZadeh's rule

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Related Items (1)

Inapproximability of shortest paths on perfect matching polytopes

Cites Work

• A counterexample to the Hirsch conjecture
• An exponential lower bound for Cunningham's rule
• A new polynomial-time algorithm for linear programming
• Worst case behavior of the steepest edge simplex method
• Linear programming, the simplex algorithm and simple polytopes
• Mathematical problems for the next century
• Automata, logics, and infinite games. A guide to current research
• A subexponential bound for linear programming
• On Friedmann's subexponential lower bound for Zadeh's pivot rule
• Random edge can be exponential on abstract cubes
• A randomized polynomial-time simplex algorithm for linear programming
• The Complexity of the Simplex Method
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
• Exponential Lower Bounds for Policy Iteration
• Polynomial algorithms in linear programming
• Theoretical Properties of the Network Simplex Method
• The Simplex Algorithm Is NP-Mighty
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Solving convex programs by random walks
• A simple polynomial-time rescaling algorithm for solving linear programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An exponential lower bound for Zadeh's pivot rule