Return to Colloquia & Seminar listing
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Algebra & Discrete Mathematics| Speaker: | Thomas Dueholm Hansen, Aarhus University |
| Location: | 2212 MSB |
| Start time: | Thu, Jun 2 2011, 4:10PM |
Description
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 on 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.