Approximation of Partial Capacitated Vertex Cover.
Reuven Bar-YehudaGuy FlysherJulián MestreDror RawitzPublished in: SIAM J. Discret. Math. (2010)
Keyphrases
- vertex cover
- approximation algorithms
- np hard
- polynomial time approximation
- approximation ratio
- special case
- precedence constraints
- lot sizing
- minimum cost
- worst case
- scheduling problem
- partial order
- optimal solution
- linear programming
- constant factor
- approximation guarantees
- planar graphs
- lower bound
- routing problem
- optimality criterion
- closed form
- spanning tree
- undirected graph