Median String Problem with Unbounded Alphabets

Given an unbounded alphabet $\Sigma$ , a set $W$ of strings over $\Sigma$ , and the Levenshtein distance between strings, find a string over $\Sigma$ that minimizes the sum of distances to the strings of $W$ .

Parameters

$n$ : number of strings

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Naive Solution	1965	$2^{O(n)}$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table