An exponential lower bound for Cunningham's rule

DOI10.1007/s10107-016-1008-4zbMath1360.90163arXiv1305.3944OpenAlexW1503025934WikidataQ115606183 ScholiaQ115606183MaRDI QIDQ507321

Oliver Friedmann, David Avis

Publication date: 3 February 2017

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

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

zbMATH Keywords

parity gamesMarkov decision processsimplex methodacyclic unique sink orientationCunningham's rule

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items

An exponential lower bound for Zadeh's pivot rule ⋮ The Polyhedral Geometry of Pivot Rules and Monotone Paths ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Cites Work

• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• The complexity of mean payoff games on graphs
• A subexponential bound for linear programming
• Finite state Markovian decision processes
• 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
• Linear programming and unique sink orientations
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Theoretical Properties of the Network Simplex Method
• The Random‐Facet simplex algorithm on combinatorial cubes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item