Projects per year
Abstract
Experimental results have suggested that evolutionary algorithms may produce higher quality solutions for instances of vertex cover than a very well known approximation algorithm for this NPcomplete problem. A theoretical analysis of the expected runtime of the (1+1)EA on a well studied instance class confirms such a conjecture for the considered class. Furthermore, a class for which the (1+1)EA takes exponential optimization time is examined. Nevertheless, given polynomial time, the evolutionary algorithm still produces a better solution than the approximation algorithm. Recently, the existence of an instance class has been proved for which the (1+1)EA produces poor approximate solutions, given polynomial time. Here it is pointed out that, by using multiple runs, the (1+1)EA finds the optimal cover of each instance of the considered graph class in polynomial time.
Original language  English 

Title of host publication  IEEE Congress on Evolutionary Computation, 2007. CEC 2007. 
Publisher  Institute of Electrical and Electronics Engineers (IEEE) 
Pages  18701877 
Number of pages  8 
ISBN (Electronic)  9781424413409 
ISBN (Print)  9781424413393 
DOIs  
Publication status  Published  1 Sept 2007 
Event  IEEE Congress on Evolutionary Computation, 2007 (CEC 2007)  Singapore, Singapore Duration: 25 Sept 2007 → 28 Sept 2007 
Conference
Conference  IEEE Congress on Evolutionary Computation, 2007 (CEC 2007) 

Country/Territory  Singapore 
City  Singapore 
Period  25/09/07 → 28/09/07 
Fingerprint
Dive into the research topics of 'Evolutionary Algorithms and the Vertex Cover Problem'. 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