Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem

Abstract

Linear programming relaxations have been used extensively in designing approximation algorithms for optimization problems. For vertex cover, linear programming and a thresholding technique gives a 2-approximate solution, rivaling the best known performance ratio. For a generalization of vertex cover we call vc ^t, in which we seek to cover t edges, this technique may not yield a feasible solution at all. We introduce a new method for massaging a linear programming solution to get a good, feasible solution for vc ^t. Our technique manipulates the values of the linear programming solution to prepare them for thresholding. We prove that this method achieves a performance ratio of 2 for vc ^t with unit weights. A second algorithm extends this result, giving a 2-approximation for vc ^t with arbitrary weights. We show that this is tight in the sense that any α-approximation algorithm for vc ^t with α < 2 implies a breakthrough α-approximation algorithm for vertex cover.

This research was supported in part by the NSERC of Canada.

This research was supported in part by the NSERC of Canada. Part of this work was done while both authors were visiting the Technion, Haifa, Israel.