Abstract: 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 analyzing the simplex method, and present upper and lower bounds on the running time.
Bio: Sophie Huiberts is a Simons Fellow at Columbia University in New York. Her research focuses on practical algorithms for solving integer programming problems, specifically on theoretically analyzing them. She did her PhD research at Centrum Wiskunde & Informatica in Amsterdam and received the Stieltjes Prize for best mathematics PhD thesis in the Netherlands.