- 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].