On the Power of Randomization in Online Algorithms
Title | On the Power of Randomization in Online Algorithms |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Ben-David, S., Borodin A., Karp R. M., Tardos G., & Wigderson A. |
Other Numbers | 587 |
Abstract | Against an adaptive adversary, we show that the power of randomization in online algorithms is severely limited! We prove the existence of an efficient ``simulation'' of randomized online algorithms by deterministic ones, which is best possible in general.The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-23.pdf |
Bibliographic Notes | ICSI Technical Report TR-90-023 |
Abbreviated Authors | S. Ben David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson |
ICSI Publication Type | Technical Report |