**Oliver Friedmann**, **Thomas Dueholm Hansen**, and **Uri Zwick** have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

**Update:** Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

**RANDOM EDGE**– Choose an improving pivoting step uniformly at random.

**RANDOM FACET**– Choose at random a facet containing your vertex and apply the algorithm in that facet.

RANDOM FACET and closely related variants which appeared in the early 90s in the works by Matousek, Sharir and Welzl and by me.

### Some background:

In the early days of linear programming it was believed that the common pivot rules

reach the optimum in a number of steps that is polynomial or perhaps even close to linear

in – the number of variables and -the number of inequalities. This belief turned out to be false: Klee and Minty found in 1972 that one of the most common variants of the simplex algorithm is exponential in the worst case. In fact, the number of pivot steps was quite close to the total number of vertices of the feasible polytope. Similar results for other pivot rules were subsequently found by many authors. And no deterministic pivot rule which requires less than exponential number of pivot steps is known.

Randomized pivot rules improved matters somewhat. RANDOM FACET and its variations had led to the the first subexponential upper bounds of the form for the expected number of pivot steps for linear programming problems with inequalities and variables. No such result for RANDOM EDGE is known.

For some background on linear programming and a description of more abstract settings for linear programming see also this post. Finding (possibly random) pivot rules which require a small number of steps for every LP problem and even for various abstract versions of LP problem is a very interesting problem. It was mentioned among quite a few other problems in the “grand plan” for “polymath3”.

Lower bounds for RANDOM EDGE and RANDOM FACET were known before only in abstract settings, and not for concrete linear programs.

### The connection to games

The path toward the proof by Friedmann, Hansen, and Zwick is exciting as well. Quoting from the abstract: The new lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. We start by building 2-player parity games (PGs) on which suitable randomized policy iteration algorithms perform a subexponential number of iterations. We then transform these 2-player games into 1-player Markov Decision Processes (MDPs) which correspond almost immediately to concrete linear programs.

Pingback: Tweets that mention Subexponential Lower Bound for Randomized Pivot Rules! | Combinatorics and more -- Topsy.com

rjliptonThanks for this post. I am quite surprised at the result, and the proof method. Seems like a major result.

Peter Bro MiltersenWhat I think is particularly interesting is that the proof grew out, in a few steps, from considerations on the strategy iteration algorithm for parity games, a topic firmly founded in formal methods (or “EuroTheory”, “ICALP track B”). In general, I think that there is way too little communication between formal methods and (non-Euro) theory and that the present proof indicates a vast unexplored potential for fruitful exchange of concepts and techniques.

Gil KalaiPost authorThank’s Dick and Peter. I also find it fastinating that the proof came from studying a special class of LP problems based on games. I did not know that the problem is founded in “Euro theory” but especially since I was in the British CS colloquium in Scotland I was quite intruiged with the relations between “Theory” and “Euro Theory”. Very interesting topic!

Gil KalaiPost authorI just added an update to the post reading:

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

Pingback: Is Complexity Theory On The Brink? « Gödel’s Lost Letter and P=NP

Christian StraubeI had the pleasure to listen to a talk of Oliver Friedmann to this paper… very interesting and enjoyable, thank you again!

Pingback: Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples. | Combinatorics and more

Pingback: Linkage « The Information Structuralist

Pingback: Is Backgammon in P? | Combinatorics and more

Pingback: Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? | Combinatorics and more