Theory Seminar

Sophie Huiberts: Smoothed analysis of the simplex method

Sophie HuibertsColumbia University
3725 Beyster BuildingMap

Passcode for Zoom: 728726

The simplex method is an important algorithm for solving linear optimization problems. The algorithm is very efficient in practice, but theoretical explanations of this fact are lacking. In this talk, I will describe smoothed analysis, one of the primary theoretical frameworks for analysing the simplex method, and present upper and lower bounds on the running time.


Greg Bodwin


Euiwoong Lee