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.