Analyses of Simple Hybrid Algorithms for the Vertex Cover Problem

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

Research output: Contribution to journalArticlepeer-review

37 Citations (SciVal)


Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast, the theoretical understanding of the interplay of different optimization methods is rare. In this paper, we make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.
Original languageEnglish
Pages (from-to)3-19
Number of pages17
JournalEvolutionary Computation
Issue number1
Publication statusPublished - 20 Nov 2009


Dive into the research topics of 'Analyses of Simple Hybrid Algorithms for the Vertex Cover Problem'. Together they form a unique fingerprint.

Cite this