title: Analyses of simple hybrid algorithms for the vertex cover problem.
abstract: 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.
authors.affiliation: Max-Planck-Institut für Informatik, Saarbrücken, Germany. tobias.friedrich@mpi-inf.mpg.de
authors.forename: Tobias
authors.initials: T
authors.lastname: Friedrich
authors.forename: Jun
authors.initials: J
authors.lastname: He
authors.forename: Nils
authors.initials: N
authors.lastname: Hebbinghaus
authors.forename: Frank
authors.initials: F
authors.lastname: Neumann
authors.forename: Carsten
authors.initials: C
authors.lastname: Witt
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated / Q000379:methods; D011336:Probability; D011340:Problem Solving; D013997:Time Factors