Constant-factor approximation of near-linear edit distance in near-linear time

Abstract

We show that the edit distance between two strings of length $n$ can be computed within a factor of $f(\epsilon )$ in $n^{1+\epsilon }$ time as long as the edit distance is at least $n^{1-\delta }$ for some $\delta (\epsilon )>0$.

40 pages, 4 figures