Approximating edit distance in near-linear time
From MaRDI portal
Publication:5172713
DOI10.1145/1536414.1536444zbMath1304.68206OpenAlexW1969844791MaRDI QIDQ5172713
Krzysztof Onak, Alexandr Andoni
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.1502
Related Items (4)
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ LCS approximation via embedding into locally non-repetitive strings
This page was built for publication: Approximating edit distance in near-linear time