- 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:
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.
- 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.