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

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

No reviews yet.

No comments yet.