Tight Approximation for Partial Vertex Cover with Hard Capacities.

Jia-Yau Shiau Mong-Jen Kao Ching-Chi Lin D. T. Lee

Published in: ISAAC (2017)

Keyphrases

vertex cover
approximation algorithms
worst case
polynomial time approximation
np hard
approximation ratio
lower bound
special case
upper bound
partial order
precedence constraints
minimum cost
constant factor
error bounds
planar graphs
closed form
theoretical analysis