Combinatorics Seminar - Sophie Huiberts (Columbia University in NYC)

16:15-18:00

Speaker: Sophie Huiberts (Columbia University in NYC)

Title: Smoothed analysis of the simplex method

Abstract: The simplex method is a combinatorial 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 one of the primary theoretical frameworks for analysing the simplex method, smoothed analysis, and present upper and lower bounds on the algorithm's running time.