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

04/10/2019

∙

by   Joshua Brakensiek, et al.

∙

0

∙

share

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.