NEAREST STRING

• INSTANCE: n strings $s_1,s_2,\ldots,s_n$, each of length m, over a finite alphabet.

• SOLUTION: A string s of length m.

• MEASURE: $\max_{i=1}^n d_H(s,s_i)$, where $d_H$ 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 $s_i$ also admits a PTAS [358].