A Practical Relaxation of Constant-Factor Treewidth Approximation Algorithms.
Mark HopkinsAdnan DarwichePublished in: Probabilistic Graphical Models (2002)
Keyphrases
- approximation algorithms
- constant factor
- upper bound
- np hard
- worst case
- special case
- lower bound
- minimum cost
- vertex cover
- primal dual
- network design problem
- approximation ratio
- randomized algorithms
- search space
- integrality gap
- linear programming relaxation
- lagrangian relaxation
- practical problems
- practical solutions