On approximation of max-vertex-cover.

Qiaoming Han Yinyu Ye Hantao Zhang Jiawei Zhang

Published in: Eur. J. Oper. Res. (2002)

Keyphrases

vertex cover
approximation algorithms
polynomial time approximation
approximation ratio
special case
np hard
constant factor
worst case
minimum cost
closed form
planar graphs
partial order
precedence constraints
optimality criterion
error bounds
approximation guarantees
undirected graph
graphical models