Concepts and Tools for Analysis of Online Algorithms

-
The cruel adversary.
-
Bi-weighted alternating directed graphs (red-black graphs).
-
Potentials.
-
Boosting.
-
Work functions, offset functions, and the opt-graph.
-
The behavioral model.
-
The distribution model.
-
Barely random algorithms.
-
Yao's Lemma.
-
The coupon collector's problem.

Back to
Course Page