On-line and Approximation Algorithms - 0368.4041

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2002/3 - Mon 10-13, Merkazei-Al 315
School of Computer Science,
Tel-Aviv University

This page will be modified during the course, and will outline the classes.

Text books:

(1) Online computation and Competitive Analysis, A Borodin and R. El-Yaniv, Camridge university press, 1998.
(2) Approximation Algorithms for NP-hard problems, edited by S. Hochbaum, PWS Publishing company, 1997.
(3) Online Algorithms - The State of the Art, edited by A. Fiat and G. Woeginger, Springer, 1998.
(4) Papers published in the last 15 years.
(5) Lecture notes from Berkeley 97 Yair Bartal
(6) Lecture notes from Brics 96 Sussane Albers

Course syllabus:

Online algorithms (algorithms that do not have all the information/input in advance) and some corresponding approximation algorithms.

Course outline

  1. Oct 14, 2002 :
    Introduction
    Examples of on-line problems
    Competitive ratio
    Ski rental problem - 2 upper/lower bounds
    Path searching problem - 9 upper/lower bounds
  2. Oct 21, 2002 :
    List update - 2 competitive MF algorithm
    List update - 2 lower bound
  3. Oct 28, 2002 :
    Paging - k competitive LRU/FIFO
    Paging - k lower bound
    k-server - k general lower bound
    k-server on the line - k competitive Double Cover algorithm
  4. Nov 4, 2002 :
    Randomized algorithms
    Ski rental - randomized upper/lower bounds
    Paging - 2H(k) competitive randomized marking algorithm
    Paging - H(k) randomized lower bound
  5. Nov 11, 2002 :
    Load balancing - identical machines
    Load balancing - related machines
  6. Nov 18, 2002 :
    Load balancing - restricted assignment - deterministic and randomized lower bound
    Load balancing - restricted assignment - upper bound
    Load balancing - unrelated machines
  7. Nov 25, 2002 :
    Virtual circuit routing
    Virtual circuit routing with durations
  8. Dec 2, 2002 :
    Virtual circuit routing with durations
    Temporary tasks - unknown durations
    Temporary tasks - identical machines
    Temporary tasks - restricted assignment
    Temporary tasks - related machines
  9. Dec 9, 2002 :
    Scheduling problems - offline approximation
  10. Dec 16, 2002 :
    Financial problems
  11. Dec 23, 2002 :
    Admission control and routing - general graphs
  12. Dec 30, 2002 :
    Admission control on the line : randomized, preemptive
    Lower bounds for admission control
  13. Jan 6, 2003 :
    Admission control on the line
  14. Jan 13, 2003 :
    Scheduling problems
    Minimum weighted matching
Last updated Jan 5, 2003