ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS

Authors
BENDAVID S BORODIN A KARP R TARDOS G WIGDERSON A
Citation
S. Bendavid et al., ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS, Algorithmica, 11(1), 1994, pp. 2-14
Citations number
17
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Applications & Cybernetics
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
11
Issue
1
Year of publication
1994
Pages
2 - 14
Database
ISI
SICI code
0178-4617(1994)11:1<2:OTPORI>2.0.ZU;2-S
Abstract
Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient ''simulation'' of randomized on-line algorithms by determ inistic ones, which is best possible in general. The proof of the uppe r bound is existential. We deal with the issue of computing the effici ent deterministic algorithm, and show that this is possible in very ge neral cases.