Publication Details
Title: On the Power of Randomization in Online Algorithms
Author: S. Ben David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson
Group: ICSI Technical Reports
Date: June 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-23.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-023
Bibliographic Reference:
S. Ben David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the Power of Randomization in Online Algorithms. ICSI Technical Report TR-90-023, June 1990
Author: S. Ben David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson
Group: ICSI Technical Reports
Date: June 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-23.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-023
Bibliographic Reference:
S. Ben David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the Power of Randomization in Online Algorithms. ICSI Technical Report TR-90-023, June 1990