Advanced Algorithms and Complexity

                                                               online algorithms

Instructor:   Adi Rosén 

Wednesday 12:45-15:45  (October-November 2008)

       Lectures 

• 22/10  - motivation ; introduction to competitive analysis;
               paging - deterministic upper bounds, lower bound (via the k-server problem)
                             randomized algorithms for paging
  
• 29/10  - Metrical Task Systems: traversal algorithms; the Work Function Algorithm; randomized algorithms
                k-server algorithm for trees
• 5/11  - The WFA for the k-server problem: proof of k-competitivness on the line and for N=k+2.
              Adversaries against randomized online algorithms and their relative power.
• 12/11  - The Comptetitive Network Throughput (CNT) model: upper and lower bound for the greedy
               protocol for Information Gathering.
               Online Metric Bipartite Matching
  

Assignments