Back to Search
Start Over
APPROXIMATING EDIT DISTANCE IN NEAR-LINEAR TIME.
- Source :
-
SIAM Journal on Computing . 2012, Vol. 41 Issue 6, p1635-1648. 14p. - Publication Year :
- 2012
-
Abstract
- We show how to compute the edit distance between two strings of length n up to a factor of 2Õ(√log n) in n1+o (1) time. This is the first subpolynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n1/3+o(1) approximation. Previously, approximation of 2Õ (√log n) was known only for embedding edit distance into l1, and it is not known if that embedding can be computed in less than quadratic time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 41
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 89522321
- Full Text :
- https://doi.org/10.1137/090767182