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

No abstract is available for this paper.

• Publication year

  2011

• Venue

  Conference on Integer Programming and Combinatorial Optimization

• Publication date

  2011-06-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-20807-2_16
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

  2011cited by this paper
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

  2011cited by this paper
• Linear Programming, the Simplex Algorithm and Simple Polytopes

  2010cited by this paper
• Exponential Lower Bounds for Policy Iteration

  2010cited by this paper
• Dynamic Programming and Optimal Control

  2010cited by this paper
• Subexponential lower bounds for randomized pivoting rules for solving linear programs

  2010influential reference
• An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it

  2009cited by this paper
• Markov Decision Processes

  2004cited by this paper
• One line and n points

  2003cited by this paper
• Automata logics, and infinite games: a guide to current research

  2002cited by this paper
• Automata Logics, and Infinite Games

  2002cited by this paper
• Linear Programming and Extensions

  2000cited by this paper
• A Discrete Strategy Improvement Algorithm for Solving Parity Games

  2000cited by this paper
• Balanced Gray Codes

  1996cited by this paper
• The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height

  1995cited by this paper
• The Number of Solutions of X^2=0 in Triangular Matrices Over GF(q)

  1995cited by this paper
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994cited by this paper
• Randomized Simplex Algorithms on Klee-Minty Cubes

  1994cited by this paper
• A subexponential randomized simplex algorithm (extended abstract)

  1992cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• Affirmative action algorithms

  1986cited by this paper
• What is the Worst Case Behavior of the Simplex Algorithm

  1980influential reference
• On Observing Nondeterminism and Concurrency

  1980cited by this paper
• Worst case behavior of the steepest edge simplex method

  1979cited by this paper
• Notes on Bland’s pivoting rule

  1978cited by this paper
• The simplex algorithm with the pivot rule of maximizing criterion improvement

  1973cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• Finite State Markovian Decision Processes

  1970cited by this paper
• Dynamic Programming and Markov Processes

  1960influential reference

• Finding Short Paths on Simple Polytopes

  2026cites this paper
• ON FLAWS IN THE EXPONENTIAL LOWER BOUNDS FOR ZADEH’S LEAST-ENTERED PIVOT RULE 1

  2025cites this paper
• An unconditional lower bound for the active-set method in convex quadratic maximization

  2025cites this paper
• Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book

  2025cites this paper
• Is Zadeh's Least-Entered Pivot Rule Exponential?

  2025cites this paper
• Optimal Smoothed Analysis of the Simplex Method

  2025cites this paper
• An unconditional lower bound for the active-set method on the hypercube

  2025cites this paper
• Reducing Stochastic Games to Semidefinite Programming

  2025cites this paper
• Attractors Is All You Need: Parity Games In Polynomial Time

  2025cites this paper
• Exponential Lower Bounds for Many Pivot Rules for the Simplex Method

  2024influential citation
• Reducing Stochastic Games to Semidefinite Program Feasibility

  2024cites this paper
• Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games

  2023cites this paper
• On the facet pivot simplex method for linear programming II: a linear iteration bound

  2022cites this paper
• Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method

  2022cites this paper
• A modified row pivot simplex algorithm

  2021cites this paper
• A Recursive Approach to Solving Parity Games in Quasipolynomial Time

  2021cites this paper
• A Double-Pivot Degenerate-Robust Simplex Algorithm for Linear Programming

  2021cites this paper
• On the facet pivot simplex method for linear programming I: algorithms and numerical test

  2021cites this paper
• (Machine) Learning to Improve the Empirical Performance of Discrete Algorithms

  2021cites this paper
• A double-pivot degenerate-tolerable simplex algorithm for linear programming

  2021cites this paper
• Priority Promotion with Parysian Flair

  2021cites this paper
• The Strahler number of a parity game

  2020cites this paper
• Universal Algorithms for Parity Games and Nested Fixpoints

  2020cites this paper
• A Universal Attractor Decomposition Algorithm for Parity Games

  2020cites this paper
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers

  2019cites this paper
• An exponential lower bound for Zadeh’s pivot rule

  2019cites this paper
• On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule

  2019cites this paper
• Spectraèdres tropicaux: application à la programmation semi-définie et aux jeux à paiement moyen. (Tropical spectrahedra: Application to semidefinite programming and mean payoff games)

  2018cites this paper
• A Parity Game Tale of Two Counters

  2018cites this paper
• Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes

  2017influential citation
• A friendly smoothed analysis of the simplex method

  2017influential citation
• Constraint Satisfaction Problems over Numeric Domains

  2017cites this paper
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

  2017cites this paper
• 49 LINEAR PROGRAMMING

  2017cites this paper
• 50 LINEAR PROGRAMMING

  2016cites this paper
• The Niceness of Unique Sink Orientations

  2016cites this paper
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes

  2016cites this paper
• Geometric random edge

  2016cites this paper
• Symmetric Strategy Improvement

  2015influential citation
• The Complexity of All-switches Strategy Improvement

  2015cites this paper
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

  2015cites this paper
• Geometric random edge

  2014cites this paper
• Algorithmic Aspects in Planning Fixed and Flexible Optical Networks With Emphasis on Linear Optimization and Heuristic Techniques

  2014cites this paper
• Recent Progress on the Complexity of Solving Markov Decision Processes

  2014cites this paper
• Improved bound on the worst case complexity of Policy Iteration

  2014cites this paper
• A Gentle Introduction to Optimization

  2014cites this paper
• Tropical aspects of linear programming

  2014cites this paper
• Lineare und Ganzzahlige Optimierung

  2014cites this paper
• About upper bounds on the complexity of Policy Iteration ∗

  2014cites this paper
• A Strongly Polynomial Reduction for Linear Programs over Grids

  2014cites this paper
• The Complexity of the Simplex Method

  2014cites this paper
• Random-Facet and Random-Bland require subexponential time even for shortest paths

  2014cites this paper
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes

  2013cites this paper
• Theoretical and computational issues for improving the performance of linear optimization methods

  2013cites this paper
• Recent progress on the combinatorial diameter of polyhedra and simplicial complexes

  2013cites this paper
• The Simplex Algorithm Is NP-Mighty

  2013cites this paper
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes

  2013cites this paper
• In defense of the Simplex Algorithm's worst-case behavior

  2013cites this paper
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

  2013cites this paper
• An exponential lower bound for Cunningham’s rule

  2013cites this paper
• Computing and proving with pivots

  2013cites this paper
• Who Solved the Hirsch Conjecture ?

  2012cites this paper
• The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes

  2012cites this paper
• DOCTEUR DE L'ÉCOLE POLYTECHNIQUE

  2012cites this paper
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs

  2012cites this paper
• Polynomial-Time Algorithms for Energy Games with Special Weight Structures

  2012cites this paper
• DRAFT March 20 , 2012 A subexponential lower bound for the Least Recently Considered rule for solving linear programs and games

  2012cites this paper
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

  2011cites this paper
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes

  2011cites this paper
• Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

  2011cites this paper
• Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes

  2011cites this paper
• OPTIMA Mathematical Optimization Society Newsletter 84

  2010cites this paper
• A counterexample to the Hirsch conjecture

  2010cites this paper