Maintaining 2-approximations for the dynamic vertex cover problem using evolutionary algorithms

Abstract

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. [7], 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.