Randomization in online computation
Steven S. Seiden · 1997
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)\approx 1.5820n - 0.5820)$-competitive. For uniform task systems, Borodin, Linial, and Saks present an algorithm which is $2H\sb2$-competitive, and show a lower bound of $H\sb{n}.$ Again using thresholding, we design a randomized algorithm which is $(H\sb{n}/{\rm ln}2 + 1 \approx 1.4427H\sb{n} + 1)$-competitive. Using a different technique we design an algorithm which is $(H\sb{n} + O(\sqrt{ logn}))$-competitive. The second problem studied is online multiprocessor scheduling. The problem of scheduling independent jobs on m machines online 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\ge 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 \ge 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.