Concepts and Tools for Analysis of Online Algorithms

  1. The cruel adversary.
  2. Bi-weighted alternating directed graphs (red-black graphs).
  3. Potentials.
  4. Boosting.
  5. Work functions, offset functions, and the opt-graph.
  6. The behavioral model.
  7. The distribution model.
  8. Barely random algorithms.
  9. Yao's Lemma.
  10. The coupon collector's problem.

Back to Course Page