Online Algorithms – Parts I and II

The following two lectures were delivered as guest lecture at GWU for graduate CS class on advanced algorithms.

  • Online Algorithms – Part I: February 16, 2011.  Covers basics of online algorithms, competitive analysis, online job scheduling, ski rental problem, and paging algorithm
  • Online Algorithms – Part II: February 23, 2011.  Covers example of randomized online algorithm, lower bound against randomization, online algorithms in machine learning (weighted majority algorithms) and a construction to show that no online graph coloring algorithm can have a constant competitive ratio.

Leave a Reply