Show simple item record Oliveto, Pietro S. He, Jun Yao, Xin 2013-07-13T04:08:27Z 2013-07-13T04:08:27Z 2009-10
dc.identifier.citation Oliveto , P S , He , J & Yao , X 2009 , ' Analysis of the (1+1)-EA for Finding Approximate Solutions to Vertex Cover Problems ' IEEE Transactions on Evolutionary Computation , vol 13 , no. 5 , pp. 1006-1029 . DOI: 10.1109/TEVC.2009.2014362 en
dc.identifier.issn 1089-778X
dc.identifier.other PURE: 764124
dc.identifier.other PURE UUID: a331dfbc-91dc-483f-93c7-abde072ea967
dc.identifier.other WOS: 000270144100005
dc.identifier.other Scopus: 70349866664
dc.identifier.other 2160/9041
dc.description.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. en
dc.format.extent 24 en
dc.language.iso eng
dc.relation.ispartof IEEE Transactions on Evolutionary Computation en
dc.rights en
dc.subject evolutionary algorithms en
dc.subject vertex cover en
dc.subject Combinatorial optimization en
dc.subject worst-case approximation en
dc.subject TIME-COMPLEXITY en
dc.subject DRIFT ANALYSIS en
dc.subject computational complexity en
dc.title Analysis of the (1+1)-EA for Finding Approximate Solutions to Vertex Cover Problems en
dc.type /dk/atira/pure/researchoutput/researchoutputtypes/contributiontojournal/article en
dc.contributor.institution Department of Computer Science en
dc.contributor.institution Advanced Reasoning Group en
dc.description.status Peer reviewed en

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Cadair

Advanced Search