|
|
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. |
|
|