Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/112245
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPourhassan, M.en
dc.contributor.authorRoostapour, V.en
dc.contributor.authorNeumann, F.en
dc.date.issued2018en
dc.identifier.citationProceedings of the IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2017), 2018 / vol.2018-January, pp.1-6en
dc.identifier.isbn1538627272en
dc.identifier.isbn9781538627273en
dc.identifier.urihttp://hdl.handle.net/2440/112245-
dc.description.abstractIn this paper, we perform theoretical analyses of the behaviour of an evolutionary algorithm and a randomised search algorithm on the dynamic vertex cover problem. The dynamic vertex cover problem has already been theoretically investigated for these two algorithms to some extent. We improve some of the existing results, i. e. we find a linear expected re-optimization time for a (1+1) EA to maintain a 2-approximation when edges are dynamically deleted from the graph. Furthermore, we investigate a different setting for the dynamic version of the problem, in which a dynamic change happens at each step with probability PD. We prove that when PD ≤ 1/(2+ϵ)em, where m is the number of edges of the graph, RLS and (1+1) EA find a 2-approximate solution from an arbitrary initial solution in expected time O(m log m). Furthermore, we prove that in expected time O(m) after the first dynamic change, they recompute a 2-approximate solution.en
dc.description.statementofresponsibilityMojgan Pourhassan, Vahid Roostapour, Frank Neumannen
dc.language.isoenen
dc.publisherIEEEen
dc.rights©2017 IEEEen
dc.source.urihttp://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8267146en
dc.titleImproved runtime analysis of RLS and (1+1) EA for the dynamic vertex cover problemen
dc.typeConference paperen
dc.identifier.rmid0030084569en
dc.contributor.conferenceIEEE Symposium Series on Computation Intelligence (SSCI 2017) (27 Nov 2017 - 01 Dec 2017 : Honolulu, HI, USA)en
dc.identifier.doi10.1109/SSCI.2017.8285391en
dc.publisher.placeNJ, USAen
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400en
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401en
dc.identifier.pubid402988-
pubs.library.collectionComputer Science publicationsen
pubs.library.teamDS03en
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidRoostapour, V. [0000-0002-8896-9590]en
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]en
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


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