Report Number: CS-TN-96-37
Institution: Stanford University, Department of Computer Science
Title: An Improved Lower Bound for Load Balancing of Tasks with Unknown Duration
Author: Plotkin, Serge
Author: Ma, Yuan
Date: October 1996
Abstract: Suppose there are n servers and a sequence of tasks, each of which arrives in an on-line fashion and can be handled by a subset of the servers. The level of the service required by a task is known upon arrival, but the duration of the service is unknown. The on-line load balancing problem is to assign each task to an appropriate server so that the maximum load on the servers is minimized. The best known lower bound on the competitive ratio for this problem was Sqrt(n). However, the argument used to prove this lower bound used a sequence of tasks with exponential duration, and therefore this lower bound does not preclude an algorithm with a competitive ratio that is polylogarithmic in T, the maximum task duration. In this paper we prove a lower bound of sqrt(T), thereby proving that a competitive ratio that is polylogarithmic in T is impossible. This should be compared to the analogous case for known-duration tasks, where it is possible to achieve competitive ratio that is logarithmic in T.
http://i.stanford.edu/pub/cstr/reports/cs/tn/96/37/CS-TN-96-37.pdf