History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees.

Rathish Das, William Kuszmaul

Browse the full SODA paper archive.