Approximating edit distance in near-linear time

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

zbMATH Keywords

approximation algorithmsedit distancemetric embeddings

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

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