On-line restricted assignment of temporary tasks with unknown durations. (Q1853182)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1856510
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On-line restricted assignment of temporary tasks with unknown durations. |
scientific article; zbMATH DE number 1856510 |
Statements
On-line restricted assignment of temporary tasks with unknown durations. (English)
0 references
21 January 2003
0 references
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 \(\Theta(m)\). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be \(\Omega(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.
0 references
On-line algorithms
0 references
Competitiveness
0 references
Temporary tasks
0 references
0 references
0.8894122242927551
0 references
0.8808911442756653
0 references
0.8808908462524414
0 references
0.8641165494918823
0 references
0.8624407649040222
0 references
