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 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+2^{- frac{n{m (1- o (1))$, and a lower bound of $1+ e^{ - frac{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+ e^{ - frac{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.)