Next: MINIMUM TREE ALIGNMENT
Up: Miscellaneous
Previous: NEAREST CODEWORD
  Index
- INSTANCE:
n strings
,
each of length m, over a
finite alphabet.
- SOLUTION:
A string s of length m.
- MEASURE:
,
where
is the Hamming distance.
- Good News:
Admits a PTAS [358].
- Comment:
Generalization in which the input strings may be longer than m and the
measure is the maxmin Hamming distance between s and a length m substring
of each
also admits a PTAS [358].
Viggo Kann
2000-03-20