Computer Science Department
School of Computer Science, Carnegie Mellon University
Non-Clairvoyant Scheduling for Mean Slowdown
Nikhil Bansal, Kedar Dhamdhere, Jochen Konemann*, Amitabh Sinha*
Resource augmentation is the concept of allowing the online algorithm a speed-up to make up for its non-clairvoyance, since the competitive ratio is obtained by comparing against an optimal offline, clairvoyant algorithm. We show that our lower bound continues to hold even with resource augmentation.
Finally, we consider the case when the ratio of job sizes (denoted B) is bounded. In this case, we show that any non-clairvoyant algorithm needs at least Omega(logB) speed up to be constant competitive. We provide an algorithm which is O(log2 B) competitive when the speed up is O(logB). In the special case when all the jobs arrive at the same time we provide an algorithm which is constant competitive and uses a O(logB) speed up.
*Graduate School of Industrial Administration, Carnegie Mellon University