Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form 2^{n^{\alpha}} 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.

Continue reading