CS 294-1: On-line Computation and Network Algorithms
The course is taught from various papers, lecture notes,
and a preliminary version of a new book by Allan Borodin and Ran El-Yaniv.
Introductions to Competitive Analysis of On-line Algorithms
can be found in the appropriate chapters of the following books:
Here is an excellent example of a scribe
- "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan.
- "Approximation Algorithms for NP-Hard Problems" by Dorit Hochbaum.
Lecture 1 (1/21/97) :
- Overview of On-line Computation
- The Ski Problem
- The Lost Cow Problem
- Competitive Analysis: Basic concepts
Lecture 2 (1/23/97) :
- 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 (Longest-Forward-Distance) is optimal off-line
- LRU (Least-Recently-Used) and FIFO (First-In-First-Out)
achieve optimal competitive ratio for deterministic on-line algorithms
Lecture 4 (1/30/97) :
- Introduction to the power of randomization in on-line 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 k-Server Problem
- The k-Server Problem.
- Lower bound of k against adaptive on-line adversaries.
- The potential function method revisited.
- Double-Coverage is k-competitive for the line metric.
Lecture 6 (2/6/97) : More on the k-Server Problem
- A k-competitive algorithm for trees.
- A 2-competitive algorithm for the 2-Server Problem.
- The optimal algorithm and work functions.
- The k+1 point case: Balance and the Work-Function Algorithm.
Lecture 7 (2/11/97) : The Harmonic k-Server Algorithm
- The Harmonic k-server algorithm is competitive.
Lecture 8 (2/13/97) : On the k-Server Conjecture
- The Work-Function k-server algorithm is 2k-1 competitive.
Lecture 9 (2/18/97) : On the k-Server Conjecture (cont.)
- Completing the Work-Function algorithm's analysis
and presenting some Open Problems.
Lecture 10 (2/20/97) : Page Migration (by M. Charikar, Stanford)
- The Page Migration problem.
- A 3-competitive randomized algorithm.
- A 5-competitive deterministic algorithm.
- A 3-competitive deterministic algorithm for uniform networks.
Lecture 11 (2/25/97) : Adversarial Queuing Theory (by Prof. J. Kleinberg,
- 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 3-competitive algorithm for uniform networks.
- The On-line 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 k-Page 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 Well-Separated Trees (k-HSTs).
- Some Applications: Mobile User Tracking, k-Server 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 k-HSTs.
Lecture 24 (4/29/97) : The List-Update Problem (by S. Albers, Max-Planck Inst.)
- The List-Accessing model, algorithms, and applications.
Lecture 25 (5/1/97) : On-line Scheduling and Load-Balancing (partially by Stefano Leonardi, Rome)
- Introduction to on-line scheduling and load-balancing.
- 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) : On-line Routing
- On-line Virtual Circuit Routing.
Homework Assignment 3 Due: 5/22/97.
, E-mail: email@example.com