Approximation algorithms for the test cover problem.
Koen M. J. De BontridderBjarni V. HalldórssonMagnús M. HalldórssonCor A. J. HurkensJan Karel LenstraR. RaviLeen StougiePublished in: Math. Program. (2003)
Keyphrases
- approximation algorithms
- np hard
- special case
- worst case
- vertex cover
- facility location problem
- network design problem
- set cover
- minimum cost
- open shop
- exact algorithms
- primal dual
- np hardness
- randomized algorithms
- approximation schemes
- approximation ratio
- precedence constraints
- search algorithm
- polynomial time approximation