COSC85/185-S96: On-Line Algorithms

Our first reference for on-line algorithms is a working draft of the book Online Computation and Competitive Analysis by Borodin and El-Yaniv. I have a draft that you can make a copy of if you like.

We introduced competitive analysis by considering the "buy-or-rent" problem, which is a special case of the 2-server problem on triangles. Optimal randomized algorithms for the 2-server problem on triangles are quite complicated, as is shown in

  author =       "C. Lund and N. Reingold",
  title =        "Linear programs for randomized on-line algorithms",
  booktitle =    "Proc. 5th ACM-SIAM Symposium on Discrete Algorithms",
  year =         "1994",
  note =         "382--391",
We then did a more involved analysis of on-line list management: the potential-function proof that move-to-front (MTF) is 2-competitive, originally from
  author =       "D. Sleator and R. E. Tarjan",
  title =        "Amortized efficiency of list update and paging rules",
  journal =      "Communications of the ACM",
  volume =       "28",
  year =         "1985",
  pages =        "202--208",
We discussed a lower bound showing that no deterministic algorithm can be less than 2-competitive, then discussed the "list-factoring" technique and used it to show the 1.75-competitiveness of the randomized BIT algorithm.
  author =       "S. Irani and N. Reingold and D. Sleator and J.
  title =        "Randomized competitive algorithms for the list update
  booktitle =    "Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms",
  year =         "1991",
  pages =        "251--260",
The best known competitive ratio for a randomized strategy is the golden ratio, about 1.6, due to Susanne Albers' TIMESTAMP-based algorithm:
  author =      "S. Albers",
  title =       "Improved Randomized On-line Algorithms for the List Update Problem",
  booktitle =    SODA94,
  pages =        "412-419",
  year =         "1994"
The above is analyzed using the list-factoring method. The best lower bound known is 1.5 - a nice open problem is to show a lower bound above 1.5 or an upper bound of 1.5, but note that one can show that a 1.5 upper bound is not provable by the list-factoring technique for 6-element lists.

We next introduced on-line routing in networks. Given a graph and a sequence of (source,sink) pairs of nodes, choose for each pair a path from the source to the sink while minimizing the congestion (the maximum number of paths through any edge). We analysed an O(log n)-competitive algorithm from Section 4 of

 title	= "On-Line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing", 
 author	= "James Aspnes and Yossi Azar and Amos Fiat and Serge Plotkin and Orli Waarts", 
 pages	= "623--631", 
 booktitle = "Proc. Twenty-Fifth Annual {ACM} Symposium on Theory of Computing", 
 year	= "1993", 
Many variations of the model are possible, including allowing "calls" to terminate, to be refused, and/or to be rerouted. For example, see
 author	= "Awerbuch and Azar and Plotkin and Waarts", 
 title	= "Competitive Routing of Virtual Circuits with Unknown Duration", 
 booktitle = "ACM-SIAM Symposium on Discrete Algorithms", 
 year	= "1994", 
One problem we mentioned but did not discuss in detail is the k-server problem. A nice open problem is to find a O(log k)-competitive randomized strategy, a good special case to consider is weighted paging.

Misc. links:

Last modified: Sat Nov 2 05:35:59 EST 2002
Neal Young <>