Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
read the original abstract
This erratum points out an error in the simplified drift theorem (SDT) [Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification of one of its conditions is sufficient to establish a valid result. In many respects, the new theorem is more general than before. We no longer assume a Markov process nor a finite search space. Furthermore, the proof of the theorem is more compact than the previous ones. Finally, previous applications of the SDT are revisited. It turns out that all of these either meet the modified condition directly or by means of few additional arguments.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
The $(1 + 1)$-EA in Dynamic Environments
Proves sharp threshold on mutation parameter χ for (1+1)-EA on Dynamic Binary Value and Uniform weight dynamic linear problems, yielding O(n log n) runtime below threshold and 2^Ω(n) above, plus a second stagnation-di...
-
Local Search on Vertex Coloring for Bipartite Graphs
Local search can return arbitrarily bad colorings on general bipartite graphs, but a gray-box operator that biases against rare colors solves complete bipartite graphs in Θ(n log n) expected time.
-
Gray-Box Optimization and the Vertex Coloring Problem
Gray-box operators enable RLS to achieve expected O(n log n) runtime for proper 2-colorings in bipartite graphs, unlike standard (1+1) EA which requires plateau guidance.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.