Technical Report CS0691

Authors: S. Ben-David, E. Dichterman
PDF - RevisedCS0691.revised.pdf
Abstract: The aim of this work is to find methods for reducing the amount of randomness needed for implementing online algorithms, without hurting their efficiency. We call an online algorithm {\em pseudo-randomized} if it uses a bounded number of random bits, regardless of its input length. We show that such algorithms can be effectively transformed into deterministic ones with a bounded increase of their competitive ratio. The main contribution of this work is the presentation of two constructible techniques for transforming randomized online algorithms into pseudo-randomized algorithms. The first technique replaces a given randomized algorithm by another that approximates its behavior. We show that such approximations result only in a bounded reduction in performance (depending upon the quality of the approximation) and that, in many cases, good approximations can be achieved by pseudo- randomized algorithms. The second technique is recycling of random bits. We introduce a notion of {\em phased algorithms} - algorithms that allow dividing any input sequence into phases such that for each phase they only use a limited amount of random bits. We show that phased algorithms can use the same random for each of the input's phases, without any loss in their performance. We apply this technique to present pseudo-randomized version of the marking algorithm for paging, which was presented by Fiat et al. [FKL$^{+}$88].
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 (, 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 1991
To the main CS technical reports page

Computer science department, Technion