Talk by Thomas Dueholm Hansen, Stanford University

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Talk by Thomas Dueholm Hansen, Stanford University.


The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear programs (Klee-Minty examples). No non-polynomial lower bounds for the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

Joint work with Oliver Friedmann and Uri Zwick.

Short bio:

Thomas Dueholm Hansen has in his PhD dissertation at Department of Computer Science, Aarhus University, demonstrated that a classic programming problem cannot be solved the way it was previously assumed

‘Can a randomised implementation of the simplex algorithm solve linear programs in polynomial time?’ Thomas has demonstrated that the answer for the most natural radomised implementation is ‘No’: ‘An algorithm is a procedure for how one asks a computer to solve a problem. And if the problem has to do with a form of optimisation where something is to be minimised, while at the same time certain conditions are fulfilled, then we talk about algorithms within linear programming,’ Thomas Dueholm Hansen explains.

With a two-year postdoc grant from The Danish council for independent research | Natural sciences – he is now continuing his basic research, in Tel Aviv and Stanford University.