Tight approximation for partial vertex cover with hard capacities.

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

Published in: Theor. Comput. Sci. (2019)

Keyphrases

vertex cover
approximation algorithms
worst case
polynomial time approximation
approximation ratio
np hard
special case
lower bound
upper bound
minimum cost
planar graphs
precedence constraints
constant factor
undirected graph
error bounds
search algorithm
closed form
optimality criterion
shortest path