Beyond Worst-Case Analysis (Lecture 19: Online Algorithms and Random Permutations)
Tim Roughgarden Lectures · 77:25
This lecture shows how to analyze online Steiner tree beyond worst-case competitive analysis: greedy is tight at \(\Theta(\log n)\) against an adversary, but if terminals are i.i.d. from an unknown distribution \(\pi\...