Online and Approximation Algorithms  0368.4041
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. ElYaniv, Camridge university press, 1998.
(2) Approximation Algorithms for NPhard 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

Oct 14, 2002 :
Introduction
Examples of online problems
Competitive ratio
Ski rental problem  2 upper/lower bounds
Path searching problem  9 upper/lower bounds

Oct 21, 2002 :
List update  2 competitive MF algorithm
List update  2 lower bound

Oct 28, 2002 :
Paging  k competitive LRU/FIFO
Paging  k lower bound
kserver  k general lower bound
kserver on the line  k competitive Double Cover algorithm

Nov 4, 2002 :
Randomized algorithms
Ski rental  randomized upper/lower bounds
Paging  2H(k) competitive randomized marking algorithm
Paging  H(k) randomized lower bound

Nov 11, 2002 :
Load balancing  identical machines
Load balancing  related machines

Nov 18, 2002 :
Load balancing  restricted assignment  deterministic and randomized lower bound
Load balancing  restricted assignment  upper bound
Load balancing  unrelated machines

Nov 25, 2002 :
Virtual circuit routing
Virtual circuit routing with durations

Dec 2, 2002 :
Virtual circuit routing with durations
Temporary tasks  unknown durations
Temporary tasks  identical machines
Temporary tasks  restricted assignment
Temporary tasks  related machines

Dec 9, 2002 :
Scheduling problems  offline approximation

Dec 16, 2002 :
Financial problems

Dec 23, 2002 :
Admission control and routing  general graphs

Dec 30, 2002 :
Admission control on the line : randomized, preemptive
Lower bounds for admission control

Jan 6, 2003 :
Admission control on the line

Jan 13, 2003 :
Scheduling problems
Minimum weighted matching
Last updated Jan 5, 2003