Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
ISBN
978-1-61197-755-4
ISSN
—
e-ISSN
—
Number of pages
17
Pages from-to
5203-5219
Publisher name
Association for Computing Machinery - Society for Industrial and Applied Mathematics
Place of publication
USA
Event location
Florence, Italy
Event date
Jan 22, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—