Linear programming relaxations have been used extensively in designing approximation algorithms for optmization 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 sup 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 sup t. Our technique manipulates the vlues of the linear programing solution to prespare them for thresholding. We prove that this method achieves a performance ratio of 2 for VC sup t with unit weights. A second algorithm extends this result, giving a 2-approximation for VC sup t with arbitrary weights. We show that this is tight in the sense that any alfa-approximation algorithm for VC sup t with alfa<2 implies a breakthrough alfa-approximation algorithm for VERTEX COVER.
展开▼
