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
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper 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 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
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.