CS 2941: Online Computation and Network Algorithms
Bibliography:
The course is taught from various papers, lecture notes,
and a preliminary version of a new book by Allan Borodin and Ran ElYaniv.
Introductions to Competitive Analysis of Online Algorithms
can be found in the appropriate chapters of the following books:
 "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan.
 "Approximation Algorithms for NPHard Problems" by Dorit Hochbaum.
Here is an excellent example of a scribe
(
latex source).
Course Schedule:

Lecture 1 (1/21/97) :
Introduction
 Overview of Online Computation
 The Ski Problem
 The Lost Cow Problem
 Competitive Analysis: Basic concepts

Lecture 2 (1/23/97) :
Amortized Analysis
 Amortized Analysis: Basic methods
 Example 1: The Binary Counter
 Example 2: 2 Stacks > Queue

Lecture 3 (1/28/97) :
The Paging Problem
 The Paging Problem.
 LFD (LongestForwardDistance) is optimal offline
 LRU (LeastRecentlyUsed) and FIFO (FirstInFirstOut)
achieve optimal competitive ratio for deterministic online algorithms

Lecture 4 (1/30/97) :
Randomized Paging
 Introduction to the power of randomization in online algorithms.
 Random Marking is O(log k) competitive against oblivious
 Yao's Principle and a lower bound for randomized
paging algorithms against oblivious adversaries.

Homework Assignment 1 Due: 2/18/97.

Lecture 5 (2/4/97) : The kServer Problem
 The kServer Problem.
 Lower bound of k against adaptive online adversaries.
 The potential function method revisited.
 DoubleCoverage is kcompetitive for the line metric.

Lecture 6 (2/6/97) : More on the kServer Problem
 A kcompetitive algorithm for trees.
 A 2competitive algorithm for the 2Server Problem.
 The optimal algorithm and work functions.
 The k+1 point case: Balance and the WorkFunction Algorithm.

Lecture 7 (2/11/97) : The Harmonic kServer Algorithm
 The Harmonic kserver algorithm is competitive.

Lecture 8 (2/13/97) : On the kServer Conjecture
 The WorkFunction kserver algorithm is 2k1 competitive.

Lecture 9 (2/18/97) : On the kServer Conjecture (cont.)
 Completing the WorkFunction algorithm's analysis
and presenting some Open Problems.

Lecture 10 (2/20/97) : Page Migration (by M. Charikar, Stanford)
 The Page Migration problem.
 A 3competitive randomized algorithm.
 A 5competitive deterministic algorithm.
 A 3competitive deterministic algorithm for uniform networks.

Lecture 11 (2/25/97) : Adversarial Queuing Theory (by Prof. J. Kleinberg,
Cornell)
 Stability results in Packet Routing.
 Adversarial Queuing Theory.
 An network that is not universally stable.
 Universally stable queuing disciplines.
 A Randomized algorithm to obtain small queues.

Lecture 12 (3/4/97) : The File Allocation Problem
 The File Allocation Problem.
 A 3competitive algorithm for uniform networks.
 The Online Steiner Tree Problem.
 The Natural Potential Function.
 A randomized reduction from File Allocation to Steiner tree.

Lecture 13 (3/11/97) : Deterministic and Distributed File Allocation
 The Greedy Steiner tree algorithm is O(log n)competitive.
 An O(log n)competitive algorithm for File Allocation.
 Competitive Distributed Algorithms.

Lecture 14 (3/13/97) : Relaxed Task Systems (by M. Charikar, Stanford)
 Metrical Task Systems and Relaxed MTS.
 Examples: The kPage Migration Problem, etc.
 An algorithm for Relaxed Task Systems.

Lecture 15 (3/18/97) : Distributed File Allocation and Distributed Paging
 Sparse Partition and their applications for Distributed Tracking.
 Distributed Paging.

Lecture 16 (3/20/97) : Distributed Paging
 The Heat & Dump algorithm for uniform networks.

Homework Assignment 2 Due: 4/8/97.

Lecture 17 (4/3/97) : Network Transmission Protocols (by D. Raz, Berkeley)
 Analysis of network transmission protocols: deterministic algorithms.

Lecture 18 (4/8/97) : Network Transmission Protocols (cont., by D. Raz, Berkeley)
 Analysis of network transmission protocols: randomized algorithms.

Lecture 19 (4/10/97) : Probabilistic Approximation of Metric Spaces
 The Metrical Task Systems model.
 Introduction to probabilistic approximation of metric spaces.

Lecture 20 (4/15/97) : Probabilistic Approximation of Metric Spaces (cont.)
 Constructing Probabilistic Partitions.

Lecture 21 (4/17/97) : Probabilistic Approximation of Metric Spaces (cont.)
 Constructing Hierarchically WellSeparated Trees (kHSTs).
 Some Applications: Mobile User Tracking, kServer Problem, Distributed Paging.

Lecture 22 (4/22/97) : Randomized Algorithms for Metrical Task Systems
 A polylog(n)competitive randomized algorithm for Metrical Task Systems.

Lecture 23 (4/24/97) : Randomized Algorithms for Metrical Task Systems (cont.)
 Completing the proof of the randomized Metrical Task Systems algorithm for kHSTs.

Lecture 24 (4/29/97) : The ListUpdate Problem (by S. Albers, MaxPlanck Inst.)
 The ListAccessing model, algorithms, and applications.

Lecture 25 (5/1/97) : Online Scheduling and LoadBalancing (partially by Stefano Leonardi, Rome)
 Introduction to online scheduling and loadbalancing.
 Identical machines, Makespan: Graham's List scheduling.
 Related machines, Makespan: A constant competitive ratio.
 Identical machines, Flow Time: the Shortest Remaining Processing Time
preemptive algorithm has logarithmic competitive ratio.

Lecture 26 (5/8/97) : Online Routing
 Online Virtual Circuit Routing.

Homework Assignment 3 Due: 5/22/97.
Yair Bartal
, Email: yair@icsi.berkeley.edu