Drift Analysis

Combinatorics Seminar
Friday, March 19, 2021 - 3:00pm for 1 hour (actually 50 minutes)
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Benjamin Doerr – Laboratoire d'Informatique (LIX), École Polytechnique
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.