Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, June 21, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Uri Zwick (Tel Aviv University)
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.
Automatic MiSe System Software Version 1.4803M | admin login