We consider load balancing in the following setting. The on-line algorithm is allowed to use n machines, whereas the optimal off-line algorithm is limited to m machines, for some fixed m < n. We show that while the greedy algorithm has a competitive ratio which decays linearly in the inverse of n/m, the best on-line algorithm has a ratio which decays exponentially in n/m. Specifically, we give an algorithm with competitive ratio of 1 + 1/2^((n/m)(1-o(1))), and a lower bound of 1 + 1/e^((n/m)(1+o(1))) on the competitive ratio of any randomized algorithm.

We also consider the preemptive case. We show an on-line algorithm with a competitive ratio of 1 + 1/e^((n/m)(1+o(1))). We show that the algorithm is optimal by proving a matching lower bound.

We also consider the non-preemptive model with temporary tasks. We prove that for n = m+1, the greedy algorithm is optimal. (It is not optimal for permanent tasks).

This is joint work with Yossi Azar and Leah Epstein.

Host: Kim Skak Larsen