Speaker: Uri Zwick

Title: New (and old) facets of the Random-Facet algorithm

Abstract: The Random-Facet pivoting rule is a randomized pivoting
rule for the simplex method used to solve linear programming (LP)
problems. It was devised independently by Kalai and by Matousek, Sharir
and Welzl. It solves any LP problem using a sub-exponential number of
pivoting steps, making it the fastest known pivoting rule for the
simplex algorithm. Following Kalai and Gärtner, we explore improved
versions of the Random-Facet pivoting rule and analyze their
performance.

Joint work with Thomas Dueholm Hansen.