Fitness levels with tail bounds for the analysis of randomized search heuristics

Research output: Contribution to journalJournal articlepeer-review

Abstract

The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected running time. Recently, upper tail bounds were added to the technique; however, these tail bounds only apply to running times that are at least twice as large as the expectation.We remove this restriction and supplement the fitness-level method with sharp tail bounds, including lower tails. As an exemplary application, we prove that the running time of randomized local search on OneMax is sharply concentrated around nlnn−0.1159...n.
Original languageEnglish
JournalInformation Processing Letters
Volume114
Issue number1-2
Pages (from-to)38-41
ISSN0020-0190
DOIs
Publication statusPublished - 2014

Keywords

  • Randomized algorithms
  • Randomized search heuristics
  • Running time analysis
  • Fitness-level method
  • Tail bounds

Fingerprint

Dive into the research topics of 'Fitness levels with tail bounds for the analysis of randomized search heuristics'. Together they form a unique fingerprint.

Cite this