✦ LIBER ✦
On-line restricted assignment of temporary tasks with unknown durations
✍ Scribed by Amitai Armon; Yossi Azar; Leah Epstein; Oded Regev
- Book ID
- 104136833
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 85 KB
- Volume
- 85
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
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 (m 2/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.