Approximating Edit Distance in Near-Linear Time

Details Approximating Edit Distance in Near-Linear Time Approximating Edit Distance in Near-Linear Time

2011-09-26

arxiv.org/abs/1109.5635v1

Computer Science

Data Structures and Algorithms

Preliminary version appeared in STOC 2009

Scientific paper

We show how to compute the edit distance between two strings of length n up to a factor of 2^{\~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^{\~O(sqrt(log n))} was known only for embedding edit distance into l_1, and it is not known if that embedding can be computed in less than quadratic time.

Affiliated with

Also associated with

No associations

Rating

Approximating Edit Distance in Near-Linear Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Edit Distance in Near-Linear Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Edit Distance in Near-Linear Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689894