Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10465182" target="_blank" >RIV/00216208:11320/23:10465182 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/1.9781611977554.ch188" target="_blank" >https://doi.org/10.1137/1.9781611977554.ch188</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611977554.ch188" target="_blank" >10.1137/1.9781611977554.ch188</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance

Popis výsledku v původním jazyce

We consider the problem of obtaining approximation algorithms for standard edit distance and Dyck edit distance that are simple, deterministic and fast, but whose approximation factor may be high. For the standard edit distance of two strings, we introduce a class of simple and fast algorithms called emph{basic single pass algorithms}. Saha (2014) gave a randomized algorithm in this class that achieves an $O(d)$ approximation on inputs $x,y$ whose edit distance is $O(d)$. In this paper, we (1) present a deterministic algorithm in this class that achieves similar performance and (2) prove that no algorithm (even randomized) in this class can give a better approximation factor. For the Dyck edit distance problem, Saha gave a randomized reduction from Dyck edit distance to standard two string edit distance at a cost of a $O(log d)$ factor where $d$ is the Dyck edit distance. We give a deterministic reduction whose description and proof are very simple.

Název v anglickém jazyce

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance

Popis výsledku anglicky

We consider the problem of obtaining approximation algorithms for standard edit distance and Dyck edit distance that are simple, deterministic and fast, but whose approximation factor may be high. For the standard edit distance of two strings, we introduce a class of simple and fast algorithms called emph{basic single pass algorithms}. Saha (2014) gave a randomized algorithm in this class that achieves an $O(d)$ approximation on inputs $x,y$ whose edit distance is $O(d)$. In this paper, we (1) present a deterministic algorithm in this class that achieves similar performance and (2) prove that no algorithm (even randomized) in this class can give a better approximation factor. For the Dyck edit distance problem, Saha gave a randomized reduction from Dyck edit distance to standard two string edit distance at a cost of a $O(log d)$ factor where $d$ is the Dyck edit distance. We give a deterministic reduction whose description and proof are very simple.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

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

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

ISBN

978-1-61197-755-4

ISSN

—

e-ISSN

—

Počet stran výsledku

17

Strana od-do

5203-5219

Název nakladatele

Association for Computing Machinery - Society for Industrial and Applied Mathematics

Místo vydání

USA

Místo konání akce

Florence, Italy

Datum konání akce

22. 1. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—