Krzysztof Onak > Papers > Approximating Edit Distance in Near-Linear Time

Approximating Edit Distance in Near-Linear Time

Authors: Alexandr Andoni, Krzysztof Onak
Conference: The 41st ACM Symposium on Theory of Computing (STOC 2009).
Journal: SIAM Journal on Computing, 41(6), 2012 (special issue on STOC 2009).

Abstract: We show how to compute the edit distance between two strings of length $n$ up to a factor of $2^{\tilde O(\sqrt{\log n})}$ in $n^{1+o(1)}$ time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art $n^{1/3+o(1)}$ approximation. Previously, approximation of $2^{\tilde O(\sqrt{\log n})}$ was known only for embedding edit distance into $\ell_1$, and it is not known if that embedding can be computed in less than quadratic time.

Update: Our new paper Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity gives a polylogarithmic approximation algorithm that runs in strongly subquadratic time.

Full version: [PDF] [PS] [arXiv]
BibTeX: [DBLP]