Additional Results
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.