- Question 7.1 Strictly speaking, (part of) Open question 7.1 was already solved before it was posed. Specifically, for a version of the page migration problem Chrobak, Larmore, Reingold and Westbrook establish a deterministic competitive lower bound of 85/27 which is approximatley 3.148 whereas previously Westbrook had given a randomized algorithm with competitive ratio 3 against an adaptive-online adversary. The references follow:
- Question 13.6 Leonardi and Vitaletti establish an $\Omega(\log \log N) = \Omega(\log D)$ for path coloring on a complete binary tree of depth $D$. They also show that randomization does not help for the problem of path coloring on the line. These results provide a partial solution to Open Question 13.6. The reference is: S. Leonardi and A. Vitaletti, ``Randomized lower bounds for online path coloring'', Proceedings of the 2nd International Workshops on on Randomization and Approximation Techniques in Computer Science (RANDOM '98), Barcelona, Spain, October 1998.

Marek Chrobak and Lawrence L. Larmore and Nick Reingold and Jeffery Westbrook Page Migration Algorithms Using Work Functions Journal of Algorithms, 24(1), pp. 124-157, July 1997.

Jeffery Westbrook Randomized Algorithms for Multiprocessor Page Migration SIAM Journal on Computing, 23(5), pp. 951-965, October 1994.

It is still open if these competitive ratios can differ by more than a constant factor.