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

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.