# CS 294-1: On-line 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 El-Yaniv. Introductions to Competitive Analysis of On-line Algorithms can be found in the appropriate chapters of the following books:
• "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan.
• "Approximation Algorithms for NP-Hard Problems" by Dorit Hochbaum.
Here is an excellent example of a scribe ( latex source).

## Course Schedule:

• Lecture 1 (1/21/97) : Introduction

• Overview of On-line 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 (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) : Randomized Paging

• 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, 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 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.
Yair Bartal , E-mail: yair@icsi.berkeley.edu