On the power of randomization in on-line algorithms |
| |
| Authors: | S Ben-David A Borodin R Karp G Tardos A Wigderson |
| |
| Affiliation: | (1) Technion, Haifa, Israel;(2) Department of Computer Science, University of Toronto, M5S 1A4 Toronto, Ontario, Canada;(3) University of California at Berkeley and International Computer Science Institute, Berkeley, CA, USA;(4) Eötvös University, Budapest, Hungary;(5) Hebrew University, Jerusalem, Israel |
| |
| 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 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.A previous version of this paper appeared in the22nd ACM STOC Conference Proceedings. Part of this research was performed while A. Borodin and A. Wigderson were visitors at the International Computer Science Institute, and while G. Tardos was a visitor at the Hebrew University. |
| |
| Keywords: | On-line algorithms Competitive analysis Randomized algorithms Game theory |
| 本文献已被 SpringerLink 等数据库收录！ |
|
