Improved approximation of maximum vertex cover

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.