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