A population-based iterated greedy algorithm for the minimum weight vertex cover problem

Given an undirected, vertex-weighted graph, the goal of the minimum weight vertex cover problem is to find a subset of the vertices of the graph such that the subset is a vertex cover and the sum of the weights of its vertices is minimal. This problem is known to be NP-hard and no efficient algorithm is known to solve it to optimality. Therefore, most existing techniques are based on heuristics for providing approximate solutions in a reasonable computation time.Population-based search approaches have shown to be effective for solving a multitude of combinatorial optimization problems. Their advantage can be identified as their ability to find areas of the space containing high quality solutions. This paper proposes a simple and efficient population-based iterated greedy algorithm for tackling the minimum weight vertex cover problem. At each iteration, a population of solutions is established and refined using a fast randomized iterated greedy heuristic based on successive phases of destruction and reconstruction. An extensive experimental evaluation on a commonly used set of benchmark instances shows that our algorithm outperforms current state-of-the-art approaches.

Figure optionsDownload as PowerPoint slideHighlights
► We propose a population-based iterated greedy algorithm for the minimum weight vertex cover problem.
► Our algorithm is the first population-based version of an iterated greedy algorithm proposed in the literature.
► Our algorithm outperforms current state-of-the-art methods not only in solution quality but also in computation time (respectively, number of solution evaluations).