On-line load balancing of temporary tasks on identical machines
- Resource Type
- Conference
- Authors
- Azai, Y.; Epstein, L.
- Source
- Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems Theory of computing and systems Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on. :119-125 1997
- Subject
- Computing and Processing
Load management
Upper bound
Polynomials
Greedy algorithms
Computer science
Algorithm design and analysis
- Language
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.