Constant Factor Approximations to Edit Distance in Nearly Linear Time
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Approx ED
Main Result
Approximating ED
Partition strings into windows
Step 0: Reduction to non-crossing matching
Note: this step crucially uses triangle inequality!
Step 1: Dense graphs via triangle inequality
Sparse graphs via "seed-and-expand"
Union of disjoint bl-cliques
Searching for matches [KS]
Sparse case CDGKS
Dense case CDGKS
Multiple levels - sparse case [KS]
Recap
Taught by
Association for Computing Machinery (ACM)