Approximation of Partial Capacitated Vertex Cover.
Reuven Bar-YehudaGuy FlysherJulián MestreDror RawitzPublished in: ESA (2007)
Keyphrases
- constant factor
- approximation algorithms
- vertex cover
- np hard
- approximation ratio
- special case
- minimum cost
- polynomial time approximation
- worst case
- precedence constraints
- optimal solution
- approximation guarantees
- scheduling problem
- integer programming
- routing problem
- branch and bound algorithm
- lot sizing
- undirected graph
- linear program
- computational complexity