Randomization in Online Computation

Final Public Oral Dissertation Defense

Steve Seiden, ICS, UC Irvine

We study the use of randomization to improve the performance of online algorithms. Two problems are examined.

First we study the metrical task system problem of Borodin,
Linial, and Saks. For this problem, these authors give a
deterministic (2*n* - 1)-competitive algorithm.
Using a technique we call thresholding, we design a randomized
algorithm which is
(*e*/(*e* - 1)*n* - 1/(*e* - 1) __
~__ 1.5820*n* - 0.5820)-competitive. For
uniform task systems, Borodin, Linial, and Saks present an
algorithm which is 2*H*_{n}-competitive, and
show a lower bound of *H*_{n}. Again using
thresholding, we design a randomized algorithm which is
(*H*_{n}/ln 2 __
~__ 1.4427*H*_{n} + 1)-competitive.
Using a different technique we design an algorithm which is
(*H*_{n} + O(sqrt log *
n*))-competitive.

The second problem studied is online multiprocessor scheduling.
The problem of scheduling independent jobs on *m* machines
originates with Graham. While the deterministic case of this
problem has been studied extensively, little work has been done on
the randomized case. For *m* = 2 a randomized
4/3-competitive algorithm was found by Bartal, Fiat, Karloff and
Vohra. A randomized algorithm for *m* __>__ 3
is presented. It achieves competitive ratios of 1.55665, 1.65888,
1.73376, 1.78295 and 1.81681, for *m* = 3, 4, 5, 6,
7 respectively. These competitive ratios are less than the best
deterministic lower bound for *m* = 3, 4, 5 and less
than the best known deterministic competitive ratio for *
m* = 3, 4, 5, 6, 7. Two models of multiprocessor
scheduling with rejection are studied. The first is the model of
Bartal, Leonardi, Marchetti-Spaccamela, Sgall and Stougie. Two
randomized algorithms for this model are presented. The first
algorithm performs well for small *m*, achieving competitive
ratios of 3/2,
(7 + sqrt 129)/10 < 1.83579,
(5 + 2 sqrt 22)/7 < 2.05441 for
*m* = 2,3,4, respectively. The second algorithm
outperforms the first for *m* __>__ 5. It
beats the deterministic algorithm of Bartal *et al.* for all
*m* = 5, ... 1000. It is conjectured that
this is true for all *m*. The second model differs in that
preemption is allowed. For this model, randomized algorithms are
presented which outperform the best deterministic algorithm for
small *m*.