A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem

The generalized vertex cover problem, an extension of classic minimum vertex cover problem, is an important NP-hard combinatorial optimization problem with a wide range of applications. The aim of this paper is to design an efficient local search algorithm with tabu strategy and perturbation mechanism to solve this problem. Firstly, we use tabu strategy to prevent the local search from immediately returning to a previously visited candidate solution and avoiding the cycling problem. Secondly, we propose the flip gain for each vertex, and then the tabu strategy is combined with the flip gain for vertex selecting. Finally, we apply a simple perturbation mechanism to help the search to escape from deep local optima and to bring diversification into the search. The experiments are carried on random instances with up to 1000 vertexes and 450,000 edges. The experimental results show that our algorithm performs better than a state-of-art algorithm in terms of both solution quality and computational efficiency in most instances.