Seminar


Date : March 9, 2023, 1:30 p.m. - Room :Salle A102

Smoothed analysis of the simplex method


Sophie HUIBERTS, post-doc - CWI - Columbia (USA)

URL vidéo : https://webtv.uca.fr/video/e420c972-7256-4838-9435-92eb29db79f4

Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.

Page web de Sophie: https://sophie.huiberts.me/