Article ID Journal Published Year Pages File Type
1143461 Operations Research Letters 2006 8 Pages PDF
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/(2q¯), where q¯ is the size of the smallest clique in a given clique-partition of the edge weighting of G.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Improved approximation of maximum vertex cover
Authors
, ,