Décembre 2022

Retour à la vue des calendrier
Jeudi 1 Décembre
Heure: 14:00 - 15:00
Lieu: https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn - code: 514019
Résumé: Smoothed analysis of the simplex method
Description: Sophie Huiberts 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 an improved upper bound on the smoothed complexity of the simplex method, as well as prove the first non-trivial lower bound on the smoothed complexity.
This is joint work with Yin Tat Lee and Xinzhi Zhang.