ICS Theory Group

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