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.
Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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.
fields
cs.NE 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
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.
citing papers explorer
-
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.