Technical Report CS0635

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
PDFCS0635.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.
CopyrightThe 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

Computer science department, Technion
admin