On-line and Approximation Algorithms - 0368.4041

-----

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2004/5 - Mon 10-13, Shenkar-physics 105
School of Computer Science,
Tel-Aviv University

-----

This page will be modified during the course, and will outline the classes.
For the outline of the course given in 2003/4 see course2003/4

Text books:

(1) Online computation and Competitive Analysis, A Borodin and R. El-Yaniv, Cambridge 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 Susanne 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 18, 2004 :
    Introduction
    Examples of on-line problems
    Competitive ratio
    Ski rental problem - 2 upper/lower bounds
    Path searching problem - 9 upper/lower bounds
  2. Oct 25, 2004 :
    List update - 2 competitive MF algorithm
    List update - 2 lower bound
  3. Nov 1, 2004 :
    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 8, 2004 :
    Randomized algorithms
    Ski rental - randomized upper/lower bounds
    Paging - 2H(k) competitive randomized marking algorithm
  5. Nov 15, 2004 :
    Paging - H(k) randomized lower bound
    Relations between different adversaries
    Load balancing - identical machines
  6. Nov 22, 2004 :
    Load balancing - related machines
    Load balancing - restricted assignment - deterministic and randomized lower bound
    Load balancing - restricted assignment - upper bound
  7. Nov 29, 2004 :
    Load balancing - unrelated machines
    Virtual circuit routing
  8. Dec 6, 2004 :
    Virtual circuit routing
    Virtual circuit routing with durations
  9. Dec 13, 2004 :
    Lower bounds for virtual circuit routing
    Scheduling problems - maximum completion time identical machines
    Scheduling problems - reduction to batch
    Scheduling problems -response time (flow time) SPT & SRPT
  10. Dec 20, 2004 :
    Scheduling problems -response time (flow time) SPT & SRPT
    Benefit problems - financial problems - upper/lower bounds
  11. Dec 27, 2004:
    Admission control on the line - classify & select
    Admission control on the line - lower bounds
    Admission control on the line - small bandwidth requirement
  12. Jan 3, 2005:
    Admission control and routing - general graphs
    Admission control on the line - lower bounds
  13. Jan 10, 2005:
    Admission control on the line : preemption
    Sixteen variants of admission control on the line
  14. Jan 17, 2005:
    Picking the winner
Last updated January 4, 2005