Constant factor approximations to edit distance on far input pairs in\n nearly linear time

2019/04/10 by Michal Koucký, Koucký, Michal, Michael Saks +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1904.05459

openalex publication_date 2019/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For any T \≥ 1, there are constants R=R(T) \≥ 1 and\n\ζ=\ζ(T)>0 and a randomized algorithm that takes as input an integer\nn and two strings x,y of length at most n, and runs in time\nO(n^1+\(1)/(T)) and outputs an upper bound U on the edit distance\nED(x,y) that with high probability, satisfies U \≤\nR(ED(x,y)+n^1-\ζ). In particular, on any input with ED(x,y) \≥\nn^1-\ζ the algorithm outputs a constant factor approximation with high\nprobability.\n A similar result has been proven independently by Brakensiek and Rubinstein\n(2019).\n

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
• Constant-factor approximation of near-linear edit distance in near-linear time
• Faster Sublinear-Time Edit Distance
• An Algorithmic Bridge Between Hamming and Levenshtein Distances
• The normalized algorithmic information distance can not be approximated