
Randomized Pivoting Rules for the Simplex Algorithm
Uri Zwick
Recorded 14 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
Abstract
The simplex algorithm is one of the most widely used algorithms for solving linear programs in practice. It's worst case complexity, however, with essentially all known deterministic pivoting rules is exponential. There is, however, a randomized pivoting rule, called Random-Facet, discovered independently by Kalai and by Matousek, Sharir and Welzl, under which the expected running time of the simplex algorithm is subexponential. We obtain subexponential lower bounds for Random-Facet and two other randomized pivoting rules.
Joint work with Thomas Dueholm Hansen and Oliver Friedmann
Watched 1181 times.
Watch