ICS Theory Group

ICS 269, Spring 1997: Theory Seminar


9 May 1997:
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 (2n - 1)-competitive algorithm. Using a technique we call thresholding, we design a randomized algorithm which is (e/(e - 1)n - 1/(e - 1)  ~ 1.5820n - 0.5820)-competitive. For uniform task systems, Borodin, Linial, and Saks present an algorithm which is 2Hn-competitive, and show a lower bound of Hn. Again using thresholding, we design a randomized algorithm which is (Hn/ln 2  ~ 1.4427Hn + 1)-competitive. Using a different technique we design an algorithm which is (Hn + 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.