Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/123972
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPourhassan, M.-
dc.contributor.authorShi, F.-
dc.contributor.authorNeumann, F.-
dc.date.issued2019-
dc.identifier.citationEvolutionary Computation, 2019; 27(4):559-575-
dc.identifier.issn1063-6560-
dc.identifier.issn1530-9304-
dc.identifier.urihttp://hdl.handle.net/2440/123972-
dc.description.abstractEvolutionary multiobjective optimization for the classical vertex cover problem has been analysed in Kratsch and Neumann (2013) in the context of parameterized complexity analysis. This article extends the analysis to the weighted vertex cover problem in which integer weights are assigned to the vertices and the goal is to find a vertex cover of minimum weight. Using an alternative mutation operator introduced in Kratsch and Neumann (2013), we provide a fixed parameter evolutionary algorithm with respect to OPT, the cost of an optimal solution for the problem. Moreover, we present a multiobjective evolutionary algorithm with standard mutation operator that keeps the population size in a polynomial order by means of a proper diversity mechanism, and therefore, manages to find a 2-approximation in expected polynomial time. We also introduce a population-based evolutionary algorithm which finds a (1+ɛ)-approximation in expected time O(n·2min{n,2(1-ɛ)OPT}+n3).-
dc.description.statementofresponsibilityMojgan Pourhassan, Feng Shi and Frank Neumann-
dc.language.isoen-
dc.publisherMassachusetts Institute of Technology Press (MIT Press)-
dc.rights© 2019 Massachusetts Institute of Technology-
dc.source.urihttps://direct.mit.edu/evco/article-abstract/27/4/559/94979/Parameterized-Analysis-of-Multiobjective?redirectedFrom=fulltext-
dc.subjectParameterized analysis-
dc.subjectglobal SEMO-
dc.subjectweighted vertex cover problem.-
dc.titleParameterized analysis of multiobjective evolutionary algorithms and the weighted vertex cover problem-
dc.typeJournal article-
dc.identifier.doi10.1162/evco_a_00255-
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400-
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401-
pubs.publication-statusPublished-
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]-
Appears in Collections:Aurora harvest 4
Computer Science publications

Files in This Item:
File Description SizeFormat 
hdl_123972.pdfAccepted version248.07 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.