Abstract
The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point 
and a linear space 
dimension k NCP asks to find a point 
that minimizes the (Hamming) distance from v: It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best e_cient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of 
for an arbitrary constant ; and a randomized algorithm that achieves an approximation ratio of 
. In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work
Contents
1. Introduction
2. An O(n/ log n)-approximation algorithm
3. A recursive O(k log(s) n/ log n)-approximation algorithm
4. The remote point problem
5. Conclusion
6.References