Analysis of the (1 + 1)-EA for finding approximate solutions to vertex cover problems

Pietro S. OLIVETO, Jun HE, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

84 Citations (Scopus)

Abstract

Vertex cover is one of the best known NP-Hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific 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 problem-specific 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 state-of-the-art 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. © 2009 IEEE.
Original languageEnglish
Pages (from-to)1006-1029
Number of pages24
JournalIEEE Transactions on Evolutionary Computation
Volume13
Issue number5
Early online date25 Sept 2009
DOIs
Publication statusPublished - Oct 2009
Externally publishedYes

Bibliographical note

This work was supported by an EPSRC grant (EP/C520696/1). Part of the work presented in this paper has previously appeared in the Proceedings of the 2007 Congress on Evolutionary Computation (CEC2007).

Keywords

  • Combinatorial optimization
  • Computational complexity
  • Evolutionary algorithms
  • Vertex cover
  • Worst-case approximation

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.

Cite this