# The Runtime of Random Local Search on the Generalized Needle Problem

arXiv: https://arxiv.org/abs/2403.08153 · HTML: https://mlsanity.com/paper/2403.08153/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 26 references that are in the map.
- First posted on arXiv 13 Mar 2024.

## Builds on (most cited first, 6 of 6)

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Precise Runtime Analysis for Plateau Functions](https://mlsanity.com/paper/1806.01331/) (2018)
- [Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments](https://mlsanity.com/paper/2006.04663/) (2020)
- [Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming](https://mlsanity.com/paper/1805.10169/) (2018)
- [Run Time Analysis for Random Local Search on Generalized Majority Functions](https://mlsanity.com/paper/2204.12770/) (2022)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)

## Built on by (most cited first, 1 of 1)

- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius k on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter k on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.