An exponential lower bound for Cunningham's rule

DOI10.1007/S10107-016-1008-4MaRDI QIDQ507321zbMATH OpenOpenAlexWikidataFDO

Authors David Avis, Oliver Friedmann

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

acyclic unique sink orientationCunningham's ruleMarkov decision processparity gamessimplex method

Mathematics Subject Classification ID

Linear programming (90C05)

Abstract: In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markhov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.

Review text

The paper proves an exponential lower bound on Cunningham's rule (least recently considered or round robin rule) in the contexts of parity games, Markov decision processes (MDPs), acyclic unique sink orientations of hypercubes (AUSOs), and linear programs (LPs). The main result of the paper is the exponential lower bound on the number of improving switches in parity games employing Cunningham's rule to move from the initial strategy to the terminal one. The authors then use a known conection between parity games and MDPs to obtain an exponential lower bound on the number of policy iterations in MDPs that use an analogue of Cunningham's rule. Then using another known connection between MDPs and LPs, the result for Cunningham's rule in LP pivoting is obtained. Finally it is hown that the parity games introduced before give rise to AUSOs, where Cunningham's rule then follows an exponentially long path. This AUSO can be realized as a polytope, in fact the same polytope that results from the transformation of the parity game to and MDP and then to an LP.

Recommendations

• 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
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Cites work

• A subexponential bound for linear programming
• 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
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Dynamic programming and optimal control. Vol. 2.
• Finite state Markovian decision processes
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• Linear programming and unique sink orientations
• On combinatorial properties of linear program digraphs
• 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
• The Random‐Facet simplex algorithm on combinatorial cubes
• Theoretical Properties of the Network Simplex Method
• What is the worst case behavior of the simplex algorithm?

Cited in

(14)

• An exponential lower bound for the latest deterministic strategy iteration algorithms
• A parity game tale of two counters
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Pivot rules for circuit-augmentation algorithms in linear optimization
• 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
• The smoothed complexity of policy iteration for Markov decision processes
• An unconditional lower bound for the active-set method on the hypercube
• A unified worst case for classical simplex and policy iteration pivot rules
• Inapproximability of shortest paths on perfect matching polytopes
• On the number of degenerate simplex pivots
• On the number of degenerate simplex pivots

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507321)