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

@InProceedings{LunRei94, 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

@Article{SleTar85, 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.

@InProceedings{IrReSW91, author = "S. Irani and N. Reingold and D. Sleator and J. Westbrook", title = "Randomized competitive algorithms for the list update problem", 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:

@INPROCEEDINGS{Albers-94, 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

@InProceedings{AspnesAFPW93, 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

@InProceedings{AwerbuchEtAl94, 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.