Please use this identifier to cite or link to this item:
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: NJ, USA
Issue Date: 2018
ISBN: 1538627272
Conference Name: IEEE Symposium Series on Computation Intelligence (SSCI 2017) (27 Nov 2017 - 1 Dec 2017 : Honolulu, HI, USA)
Statement of
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
DOI: 10.1109/SSCI.2017.8285391
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
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.