CS 294-1: On-line Computation and Network Algorithms

Bibliography:

• "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan.
• "Approximation Algorithms for NP-Hard Problems" by Dorit Hochbaum.

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
  
  
  • Check this for discussion on Page Replacement Policies.
  
  
• 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