Abstract
In the last decade there has been an ongoing interest in string comparison problems. Particular attention has been given to the problem of {\em sorting by reversals} ({\SBR}): given two strings, $A$ and $B$, find the minimum number of reversals that transform the string $A$ into the string $B$ (a {\em reversal} $\rho(i,j)$, $i.lt.j$, transforms a string $A=a_1\ldots a_n$ into a string $A'=a_1\ldots a_{i-1} a_{j} a_{j-1} \ldots a_{i} a_{j 1} \ldots a_n$).
In this paper we consider the problem $k$-{\SBR}, a version of {\SBR} in which each symbol is allowed to appear up to $k$ times in each string, for some $k\geq 1$. The main result of the paper is a $\Theta(k)$-approximation algorithm for $k$-{\SBR} running in time $O(n)$, compared to the previously known algorithm for $k$-{\SBR}, this is an improvement by a factor of $\Theta(k)$ in the approximation ratio, and by a factor of $\Theta(k)$ in the running time.