Stee. Resource augmentation in load balancing

We consider load balancing in the following setting. The on-line algorithm is allowed to use n machines, whereas the optimal o-line algorithm is limited to m machines, for some xed 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. Specically, we give a determin-istic algorithm with competitive ratio of 1 + 2