On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
Mojgan Pourhassan, Tobias Friedrich, Frank Neumann · 2017
We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1)EA achieve this goal in expected pseudo-polynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2-approximation in expected polynomial time while the one+one still encounters a pseudo-polynomial lower bound.