Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Improved runtime analysis of RLS and (1+1) EA for the dynamic vertex cover problem|
|Citation:||Proceedings of the IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2017), 2018 / vol.2018-January, pp.1-6|
|Publisher Place:||Piscataway, NJ|
|Conference Name:||IEEE Symposium Series on Computation Intelligence (SSCI 2017) (27 Nov 2017 - 01 Dec 2017 : Honolulu, HI, USA)|
|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.|
|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.