Theory Seminar

Sophie Huiberts: Smoothed analysis of the simplex method

Sophie HuibertsColumbia University
WHERE:
3725 Beyster Building
SHARE:

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.

Organizer

Greg Bodwin

Organizer

Euiwoong Lee