Improved approximation of maximum vertex cover

Improved approximation of maximum vertex cover

0.00 Avg rating0 Votes
Article ID: iaor20061797
Country: Netherlands
Volume: 34
Issue: 1
Start Page Number: 77
End Page Number: 84
Publication Date: Jan 2006
Journal: Operations Research Letters
Authors: ,
Abstract:

We provide a new LP relaxation of the maximum vertex cover problem and a polynomial-time algorithm that finds a solution within the approximation factor 1-1/(2&qmacr;), where &qmacr; is the size of the smallest clique in a given clique-partition of the edge weighting of G.

Reviews

Required fields are marked *. Your email address will not be published.