I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.

Is there an algorithm for finding the string $x$ which minimizes the sum of the distances to all strings in $S$, that is

$\arg_x \min \sum_{s \in S} \text{edit-distance}(x,s)$

It seems like there should, but I can't find the right reference.


1 Answer 1


The problem is known as "median string problem" and it is NP-complete; some results can be found searching with Google; in particular "2-Approximation Algorithms for Median and Centre String Problems". If $x$ must be one of the points in $S$ then the problem becomes solvable in polynomial time.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.