Completed
Note: this step crucially uses triangle inequality!
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Constant Factor Approximations to Edit Distance in Nearly Linear Time
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Approx ED
- 3 Main Result
- 4 Approximating ED
- 5 Partition strings into windows
- 6 Step 0: Reduction to non-crossing matching
- 7 Note: this step crucially uses triangle inequality!
- 8 Step 1: Dense graphs via triangle inequality
- 9 Sparse graphs via "seed-and-expand"
- 10 Union of disjoint bl-cliques
- 11 Searching for matches [KS]
- 12 Sparse case CDGKS
- 13 Dense case CDGKS
- 14 Multiple levels - sparse case [KS]
- 15 Recap
