Title :
On-line load balancing of temporary tasks on identical machines
Abstract :
We prove an exact lower bound of 2-1/m on the competitive ratio of any deterministic algorithm for load balancing of temporary tasks on m identical machines. We also show a lower bound of 2-1/m for randomized algorithms for small m and 2-2/m+1 for general m. If in addition, we restrict the sequence to polynomial length, then the lower bound for randomized algorithms becomes 2-O(log log m/log m) for general m
Keywords :
competitive algorithms; computational complexity; deterministic algorithms; randomised algorithms; resource allocation; scheduling; competitive ratio; deterministic algorithm; exact lower bound; identical machines; online load balancing; polynomial length; randomized algorithms; scheduling; temporary tasks; Algorithm design and analysis; Computer science; Greedy algorithms; Load management; Polynomials; Upper bound;
Conference_Titel :
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location :
Ramat-Gan
Print_ISBN :
0-8186-8037-7
DOI :
10.1109/ISTCS.1997.595163
