Resource Augmentation in Load Balancing. Software Engineering

摘要

The authors consider load-balancing in the following setting. The on-line211u001ealgorithm is allowed to use n machines, whereas the optimal off-line algorithm is 211u001elimited to m machines, for some fixed m < n. We show that while the greedy 211u001ealgorithm has a competitive ratio which decays linearly in the inverse of n/m, 211u001ethe best on-line algorithm has a ratio which decays exponentially in n/m. 211u001eSpecifically, we give an algorithm with competitive ratio of 1 + 2 n/m (1-o(1)), 211u001eand a lower bound of 1 + e-n/m (1 + o(1)) on the competitive ratio of any 211u001erandomized algorithm. We also consider the preemptive case. We show an on-line 211u001ealgorithm with a competitive ratio of 1 + e-n/m(1 +o(1)). We show that the 211u001ealgorithm is optimal by proving a matching lower bound. We also consider the 211u001epreemptive case. We show an on-line algorithm with a competitive ratio of 1 + e-211u001en/m (1+o(1)). We show that the algorithm is optimal by proving a matching lower 211u001ebound. We also consider the non-preemptive model with temporary tasks. We prove 211u001ethat for n= m + 1, the greedy algorithm is optimal. (It is not optimal for 211u001epermanent tasks).