| TR#: | CS0635 |
| Class: | CS |
| Title: | ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS |
| Authors: | S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson |
| CS0635.pdf | |
| 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. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0635), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1990
To the main CS technical reports page