Sophie Huiberts: Smoothed analysis of the simplex method

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.