An experimental comparison of three heuristics for the WVCP

The modification of the greedy algorithm for the weighted vertex cover problem (WVCP) suggested by Clarkson yields an algorithm with better worst-case performance. The results presented in this paper indicate, however, that the generic greedy algorithm performs far better on the average than the modified algorithm. Even so, the generic greedy algorithm produces solutions which are on the average several percent above optimum, and which cannot be improved by additional runs due to the deterministic nature of the algorithm. The nondeterministic Simulated Annealing algorithm has therefore been specialized to the WVCP. The Simulated Annealing algorithm yields solutions of higher quality, even when only a moderate number of iterations are performed.