6
$\begingroup$

Input: a bunch of binary strings: x_0, x_1, ... , x_n

Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. the minimum number of insertions, deletions, and substitutions to transform x into y.

What complexity class is this problem in? Does it have an efficient exact or approximation algorithm?

$\endgroup$
  • 1
    $\begingroup$ The problem for Hamming distance is called Hamming center problem and it is NP-complete. $\endgroup$ – Mohammad Al-Turkistany Sep 17 '16 at 0:14
8
$\begingroup$

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.

$\endgroup$
  • $\begingroup$ Technically, it's an NPO problem. Thanks! $\endgroup$ – user42537 Sep 21 '16 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy