Beyond Worst-Case Analysis (Lecture 17: Self-Improving Algorithms)
Tim Roughgarden Lectures · 85:12
Self-improving algorithms assume inputs are i.i.d. from an unknown distribution and, after seeing a modest number of samples, evolve to match the performance of an algorithm that knew that distribution in advance. Thi...