Theory Seminar
Sophie Huiberts: Smoothed analysis of the simplex method
Sophie HuibertsColumbia University
WHERE:
3725 Beyster Building
WHEN:
Friday, January 27, 2023 @ 3:00 pm - 4:00 pm
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
WEB: Event Website
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.