@inproceedings{5cd9b1fba51140538f7cdb451f6d240d,
title = "Improved fixed-budget results via drift analysis",
abstract = "Fixed-budget theory is concerned with computing or bounding the fitness value achievable by randomized search heuristics within a given budget of fitness function evaluations. Despite recent progress in fixed-budget theory, there is a lack of general tools to derive such results. We transfer drift theory, the key tool to derive expected optimization times, to the fixed-budged perspective. A first and easy-to-use statement concerned with iterating drift in so-called greed-admitting scenarios immediately translates into bounds on the expected function value. Afterwards, we consider a more general tool based on the well-known variable drift theorem. Applications of this technique to the LeadingOnes benchmark function yield statements that are more precise than the previous state of the art.",
author = "Timo K{\"o}tzing and Carsten Witt",
year = "2020",
doi = "10.1007/978-3-030-58115-2_45",
language = "English",
isbn = "9783030581145",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "648--660",
editor = "Thomas B{\"a}ck and Mike Preuss and Andr{\'e} Deutz and Michael Emmerich and Hao Wang and Carola Doerr and Heike Trautmann",
booktitle = "Parallel Problem Solving from Nature",
note = "16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 ; Conference date: 05-09-2020 Through 09-09-2020",
}