"512950" . "000232273200050" . . "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)$."@en . "11320" . . "[117337BAA1EC]" . . . "2005-01-01+01:00"^^ . . . . . . . . . . "Approximating Reversal Distance for Strings with Bounded Number of Duplicates" . "3-540-28702-7" . . . "Kolman, Petr" . "RIV/00216208:11320/05:00206164!RIV10-MSM-11320___" . "P(1M0545), Z(MSM0021620838)" . "Approximating Reversal Distance for Strings with Bounded Number of Duplicates"@en . "1"^^ . "Approximating; Reversal; Distance; Strings; Bounded; Number; Duplicates"@en . . "1"^^ . . "RIV/00216208:11320/05:00206164" . "Berlin" . "Berlin" . . "Springer-Verlag" . "Approximating Reversal Distance for Strings with Bounded Number of Duplicates"@en . "Approximating Reversal Distance for Strings with Bounded Number of Duplicates" . . "Mathematical Foundations of Computer Science 2005, proceedings" . . . "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)$." . "11"^^ . .