Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/112245
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Improved runtime analysis of RLS and (1+1) EA for the dynamic vertex cover problem
Author: Pourhassan, M.
Roostapour, V.
Neumann, F.
Citation: Proceedings of the IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2017), 2018 / vol.2018-January, pp.1-6
Publisher: IEEE
Publisher Place: Piscataway, NJ
Issue Date: 2018
ISBN: 1538627272
9781538627273
Conference Name: IEEE Symposium Series on Computation Intelligence (SSCI 2017) (27 Nov 2017 - 01 Dec 2017 : Honolulu, HI, USA)
Statement of
Responsibility: 
Mojgan Pourhassan, Vahid Roostapour, Frank Neumann
Abstract: In 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.
Rights: ©2017 IEEE
RMID: 0030084569
DOI: 10.1109/SSCI.2017.8285391
Grant ID: http://purl.org/au-research/grants/arc/DP140103400
http://purl.org/au-research/grants/arc/DP160102401
Published version: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8267146
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.