Online algorithms (Randomized algorithms, Fall 2022, Lecture 26)
Kent Quanrud · 71:00
This lecture shows why randomization helps in online algorithms: for caching, deterministic marking (NRU/LRU) is only \(k\)-competitive, but randomly evicting an unmarked page improves the expected ratio to \(O(\log k...