Next: NEAREST STRING
Up: Miscellaneous
Previous: MINIMUM DECISION TREE
  Index
- 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 [35].
- Comment:
Not approximable within
for any
unless NP
QP [35].
The complementary maximization problem, where the number of bits that
agree between x and y is to be maximized, does not admit a
PTAS [399].
Viggo Kann
2000-03-20