## On the Power of Barely Random Online Algorithms

Steve Seiden, Technische Universität Graz, Institut für
Mathematik B

(Joint work with John Noga.)

A barely random online algorithm is one which is distribution
over some constant number of deterministic algorithms. An oblivious
barely random online algorithm is a barely random online algorithm
which chooses its distribution prior to serving the first request.
Although a number of barely random algorithms have been presented
in the literature, there has been, up to this point, no formal
study of the properties of this class. Most researchers would
probably agree that such algorithms are desirable, in that they
conserve a precious resource---random bits. Such algorithms are
also desirable in that they are generally easier to analyze than
algorithms which use an unbounded number of random choices.
However, it is important to consider the possible tradeoffs. The
formal study of barely random online algorithms is initiated here.
It is shown that barely random online algorithms are, under certain
restrictions, no more powerful than oblivious barely random online
algorithms. A general technique for proving lower bounds for barely
random online algorithms is presented. This technique is an
application of the well known von Neumann/Yao principle. For
several simple online problems, lower and upper bounds for barely
random online algorithms are given. The power of barely random
algorithms for the ski rental problem is completely characterized.
Other problems investigated include paging, total completion time
scheduling, m-machine scheduling, interval scheduling and the cow
path problem.

### Thursday, April 30, 1998, 1:00PM, in ICS 432