On-line load balancing
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 218-225
- https://doi.org/10.1109/sfcs.1992.267770
Abstract
The setup for the authors' problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned can not be re-assigned. They make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. The authors derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely /sup (3n)2/3///sub 2/(1+o(1)), and derive a lower bound, Omega ( square root n), for any other deterministic or randomized on-line algorithm.Keywords
This publication has 7 references indexed in Scilit:
- On-line scheduling in the presence of overloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Randomized online graph coloringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New algorithms for an ancient scheduling problemPublished by Association for Computing Machinery (ACM) ,1992
- An optimal algorithm for on-line bipartite matchingPublished by Association for Computing Machinery (ACM) ,1990
- An on-line graph coloring algorithm with sublinear performance ratioDiscrete Mathematics, 1989
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier ,1979
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966