Online Algorithms and Competitive Analysis
(236603 - Advanced Topics in CS)
Place and Time: Taub 8; Tue. 10:30-12:30 (Winter 2001/2002)
Lectures
(please read the
notes with a grain of suspicion...)
-
23/10 - motivation ; introduction ; list accesing
-
30/10 - (notes)
list accesing; Move-To-Front; Bit
-
(Strike)
-
4/12 - Paging: marking algorithms; randomized marking
-
11/12 - Paging: variable sizes/variable costs
-
18/12 - (notes)
Paging: access graphs; Far. Request-Answer games, adversaries
-
25/12 - The relative power of adversaries
-
1/1 - (notes)
Searching and Navigation (Cow and Wall problems)
-
8/1 - (notes)
Metrical Task Systems: Travelsal algorithms; the Work Function Algorithm
-
15/1 - (notes)
Proof of WFA for MTS. The k-server problem: lower bound, definition
of WFA, DC for the line
-
22/1 - (notes)
k-server: randomized algorithm for the cycle. Load balancing: indentical
machines; related machines; restricted machines
-
29/1 - (notes)
Load balancing: restricted machines; unrelated machines.
-
5/2 - (notes)
call admission; online independent set; online graph coloring