Publication Date:
2006
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\bar q),
where \bar q is the size of the smallest clique in a given
clique-partition of the edge weighting of G.
Iris type:
01.01 Articolo in rivista
Keywords:
vertex cover; polyhedra; approximation algorithm
List of contributors:
Nobili, Paolo; Galluccio, Anna
Published in: