Drift Analysis

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.