Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00206144" target="_blank" >RIV/00216208:11320/06:00206144 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set
Original language description
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_1ldots a_n$ into a string $A'=a_1ldots 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 $kgeq 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.
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)