Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

DOI10.1145/3422823MaRDI QIDQ5056449zbMATH OpenOpenAlexFDO

Authors Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael Saks

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.03664

zbMATH Keywords

approximation algorithmedit distancerandomized algorithmsub-quadratic-time algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Abstract: Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within an approximation factor $extpoly(logn)$. In this paper, we provide an algorithm with running time $ildeO(n^{2-2/7})$ that approximates the edit distance within a constant factor.

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• A sublinear algorithm for weakly approximating edit distance
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

Cited in

(21)

• k-approximate quasiperiodicity under Hamming and edit distance
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• A sublinear algorithm for weakly approximating edit distance
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Approximating edit distance in near-linear time
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Constant-factor approximation of near-linear edit distance in near-linear time
• Approximating edit distance in near-linear time
• Weak inverse neighborhoods of languages
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Quantum bounds for 2D-grid and Dyck language
• Near-optimal quantum algorithms for string problems
• Locally consistent decomposition of strings with applications to edit distance sketching
• Weighted edit distance computation: strings, trees, and Dyck
• A weak inverse of language neighborhoods and its properties
• Sequential pattern detection: similarities and differences across various fields
• Approximating dynamic time warping distance between run-length encoded strings
• Many flavors of edit distance

This page was built for publication: Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056449)