Approximating Reversal Distance for Strings with Bounded Number of Duplicates

Abstrakt

For a string $A=a_1\ldots a_n$, a {\em reversal} $\rho(i,j)$, $1\leq i lt \leq n$, reverses the order of symbols in the substring $a_i\ldots a_j$ of $A$. Given two strings, $A$ and $B$, {\em sorting by reversals} is the problem of finding the minimum number of reversals that transform the string $A$ into the string $B$.

Traditionally, the problem was studied for permutations. We consider a generalization of the problem and allow each symbol to appear at most $k$ times in each string. The main result of the paper is a $\Theta(k^2)$-approximation algorithm running in time $O(kn)$.