Deterministic approximation algorithms for the nearest codeword problem.
Noga AlonRina PanigrahySergey YekhaninPublished in: Algebraic Methods in Computational Complexity (2009)
Keyphrases
- approximation algorithms
- randomized algorithms
- np hard
- special case
- vector quantization
- approximation guarantees
- minimum cost
- vertex cover
- network design problem
- facility location problem
- approximation schemes
- open shop
- worst case
- primal dual
- exact algorithms
- constant factor
- approximation ratio
- set cover
- lower bound
- disjoint paths
- data points
- computational complexity
- precedence constraints