Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.

Michal Kouck, Michael E. Saks

Browse the full SODA paper archive.