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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The problem for Hamming distance is called Hamming center problem and it is NP-complete. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Sep 17, 2016 at 0:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Technically, it's an NPO problem. Thanks! $\endgroup$
    – user42537
    Commented Sep 21, 2016 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.