A sublinear algorithm for weakly approximating edit distance

DOI10.1145/780542.780590zbMath1192.68872OpenAlexW2133601898MaRDI QIDQ3581249

Funda Ergün, Sofya Raskhodnikova, Joe Kilian, Avner Magen, Rahul Sami, Ronitt Rubinfeld, Tuğkan Batu

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780590

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence, Surprises in approximating Levenshtein distances, The power and limitations of uniform samples in testing properties of figures, Quantum pattern matching fast on average, Testing permutation properties through subpermutations, Nonembeddability theorems via Fourier analysis, The intractability of computing the Hamming distance, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Tolerant property testing and distance approximation