Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs
Marek KarpinskiRichard SchmiedClaus ViehmannPublished in: CoRR (2011)
Keyphrases
- vertex cover
- approximation algorithms
- worst case
- lower bound
- upper bound
- np hard
- constant factor
- error bounds
- polynomial time approximation
- approximation ratio
- approximation guarantees
- minimum cost
- special case
- branch and bound
- greedy algorithm
- branch and bound algorithm
- graph theory
- optimal solution
- log likelihood
- lower and upper bounds
- maximum likelihood
- computational complexity