Abstract
We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is Θ(√m). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be Ω(m2/3). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of m. We also show that for a small number of machines, namely m ≤ 5, the greedy algorithm is optimal.
Original language | English (US) |
---|---|
Pages (from-to) | 67-72 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 85 |
Issue number | 2 |
DOIs | |
State | Published - Jan 31 2003 |
Keywords
- Competitiveness
- On-line algorithms
- Temporary tasks
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications