Projects per year
Abstract
Vertex cover is one of the best known NPHard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problemspecific ones. A theoretical analysis that explains these empirical results is presented concerning the random local search algorithm and the (1 + 1)EA. Since it is not expected that an algorithm can solve the vertex cover problem in polynomial time, a worst case approximation analysis is carried out for the two considered algorithms and comparisons with the best known problemspecific ones are presented. By studying instance classes of the problem, general results are derived. Although arbitrarily bad approximation ratios of the (1 + 1)EA can be proved for a bipartite instance class, the same algorithm can quickly find the minimum cover of the graph when a restart strategy is used. Instance classes where multiple runs cannot considerably improve the performance of the (1 + 1)EA are considered and the characteristics of the graphs that make the optimization task hard for the algorithm are investigated and highlighted. An instance class is designed to prove that the (1 + 1)EA cannot guarantee better solutions than the stateoftheart algorithm for vertex cover if worst cases are considered. In particular, a lower bound for the worst case approximation ratio, slightly less than two, is proved. Nevertheless, there are subclasses of the vertex cover problem for which the (1 + 1)EA is efficient. It is proved that if the vertex degree is at most two, then the algorithm can solve the problem in polynomial time.
Original language  English 

Pages (fromto)  10061029 
Number of pages  24 
Journal  IEEE Transactions on Evolutionary Computation 
Volume  13 
Issue number  5 
DOIs  
Publication status  Published  1 Oct 2009 
Keywords
 evolutionary algorithms
 vertex cover
 Combinatorial optimization
 worstcase approximation
 computational complexity
Fingerprint
Dive into the research topics of 'Analysis of the (1+1)EA for Finding Approximate Solutions to Vertex Cover Problems'. Together they form a unique fingerprint.Projects
 1 Finished

Computational Complexity Analysis of Evoloutionary Algarithms.
Engineering & Physical Science Research Council
1/05/05 → 31/10/08
Project: Research Councils