Next: MINIMUM TREE ALIGNMENT Up: Miscellaneous Previous: MINIMUM DECISION TREE Index

### NEAREST CODEWORD

- INSTANCE: Linear binary code C of length n and a string x of length n.

- SOLUTION: A codeword y of C.

- MEASURE: The Hamming distance between x and y, i.e., d(x,y).

- Bad News: Not in APX [33].

- Comment: Not approximable within for any unless NPQP [33]. The complementary maximization problem, where the number of bits that agree between x and y is to be maximized, does not admit a PTAS [377].