# Find a string with minimal edit distance from a set of given strings

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?

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