Maintaining 2-Approximations for the Dynamic Vertex Cover Problem Using Evolutionary Algorithms
Mojgan Pourhassan, Wanru Gao, Frank Neumann · 2015
Evolutionary algorithms have been frequently used to deal with dynamic optimization problems, but their success is hard to understand from a theoretical perspective. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for dynamic combinatorial optimization problems. We examine a dynamic version of the classical vertex cover problem and analyse evolutionary algorithms with respect to their ability to maintain a 2-approximation. Analysing the different evolutionary algorithms studied by Jansen et al. (2013), we point out where two previously studied approaches are not able to maintain a 2-approximation even if they start with a solution of that quality. Furthermore, we point out that the third approach is very effective in maintaining 2-approximations for the dynamic vertex cover problem.