  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$.
