Next: NEAREST STRING
Previous: MINIMUM DECISION TREE
Linear binary code C of length n and a string x of length n.
A codeword y of C.
The Hamming distance between x and y, i.e., d(x,y).
- Bad News:
Not in APX .
Not approximable within
unless NPQP .
The complementary maximization problem, where the number of bits that
agree between x and y is to be maximized, does not admit a