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

2019/04/10 by Brakensiek, Joshua, Rubinstein, Aviad · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1904.05390

Abstract

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.

Cited by

• Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance

Related

• Edit Distance in Near-Linear Time: it's a Constant Factor
• Approximating Edit Distance in Near-Linear Time
• Approximating Edit Distance in the Fully Dynamic Model
• RLE edit distance in near optimal time
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless\n SETH is false)