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

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2006

Kód důvěrnosti údajů

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

Název statě ve sborníku

Approximation and Online Algorithms

ISBN

978-3-540-69513-4

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Berlin

Datum konání akce

1. 1. 2006

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000244556500022