2013/07/16 by Carsten Witt, Witt, Carsten
Computer Science · #FOS: Computer and information sciences #Machine Learning and Algorithms #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Optimization and Search Problems #cs.NE
paper · pdf · doi:10.48550/arxiv.1307.4274
8 pages
arxiv created 2013/07/16 · openalex publication_date 2013/07/16 · arxiv updated 2013/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 n ln n - 0.1159 n.