# Relevant to Online Computation and Compettitive Analysis

This page contains a list of new results that are relevant to the book. Some are known results that were omitted from the book and some are new results sometimes solving an open problem mentioned in the book.

• List accessing randomized lower bound: In the historical section (2.6) for randomized list accessing we state the 1.5 lower bound due to Teia. For the partial cost model, Ambuhl, Gartner and von Stengel (click here for an online reference) have been able to achieve a lower bound of 1.5003.
• Theorem 9.11 has now been improved by Bartal (STOC 98, pp 161-168) as follows: Every N point metric space can be alpha-probabilistically approximated by h-HSTs with alpha = O(h log N loglogN). Consequently, Corollary 9.12 is also improved by a log N factor yielding: For every N-point space M, there is a c'-competitive MTS algorithm with c' = O((log^5 N)/loglog N).
• Relating to Open Question 11.1: Bartal, Chrobak and Larmore have shown that for k=2 servers on the continuous real line, there is a randomized algorithm which is 158/78- competitive (i.e. the first algorithm achieving a competitive ratio less than 2 competitive against an oblivious adversary for a space with more than 3 points). This result follows from a study of a variant of the k-server problem in which every request must be served by l of the k servers. The reference is: Y. Bartal, Chrobak, M. and Larmore, L.L., ``A Randomized Algorithm for Two Serers on the Line,'' Proceedings of European Symposium on Algorithms (ESA), August 1998.
• With regard to section 11.5: we should have mentioned the following result due to Chrobak and Larmore: For k = 2 and for every metric space, HARMONIC is 3-competitive (against an adaptive adversary). Theorem 11.5 shows that this is the optimal ratio for HARMONIC in the case of k=2. The reference for this result is: Chrobak, M. and Larmore, L.L., ``HARMONIC is 3-competitive for two servers,'' Theoretical Computer Science {98}, 1992 pp. 339-346.
• With respect to section 12.2: For the problem of load balancing of permanent jobs on N identical machines, it was known that randomization provably helps for N=2 (optimal randomized competitive ratio of 4/3 as contasted with optimal deterministic ratio of 3/2) but not known if randomization helps for N > 2. Seiden has shown that randomization provably helps for N =3, 4, 5. The randomized competitive ratios for these cases are (respectively, 1.55665, 1.65888, and 1.73376) are better than the correspinding deterministic lower bounds. Seiden has also given randomized algorithms for N = 6, 7 beating the best known deterministic upper bounds. The reference is : Seiden, ``Randomized algorithms for that ancient scheduling problem'', Proceedings of the 5th Workshop on Algorithms and Data Structures, August 1997, pp 210-223.