DocumentCode
2263885
Title
On-line load balancing of temporary tasks on identical machines
Author
Epstein, Leah
fYear
1997
fDate
17-19 Jun 1997
Firstpage
119
Lastpage
125
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ISTCS.1997.595163
Filename
595163
Link To Document