Temporary tasks assignment resolved

Temporary tasks assignment resolved

0.00 Avg rating0 Votes
Article ID: iaor2005374
Country: United States
Volume: 36
Issue: 3
Start Page Number: 295
End Page Number: 314
Publication Date: Jul 2003
Journal: Algorithmica
Authors: , , ,
Keywords: load balancing
Abstract:

Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem existed for almost a decade. We resolve this problem by providing an inapproximability result. In addition, a newer open question is to identify the dependency of the competitive ratio on the durations of jobs in the case where durations are known. We resolve this problem by characterizing this dependency. Finally, we provide a PTAS for the off-line problem with a fixed number of machines and show a 2-inapproximability result for the general case.

Reviews

Required fields are marked *. Your email address will not be published.