- Series
- Combinatorics Seminar
- Time
- Friday, March 19, 2021 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
- Speaker
- Benjamin Doerr – Laboratoire d'Informatique (LIX), École Polytechnique
- Organizer
- Lutz Warnke
Drift analysis is the name for a collection of tools that allow to translate information about the one-step progress of a randomized process into information about first hitting times. Drift analysis is successfully used in the mathematical analysis of randomized search heuristics, most notably, evolutionary algorithms, but (for unclear reasons) much less in discrete mathematics or other areas of algorithms.
In this talk, I will give a brief introduction to drift analysis, show some classic and recent applications, and describe some open problems, both concerning drift methods and the mathematical runtime analysis of randomized search heuristics.