TY - GEN
T1 - Temporary tasks assignment resolved
AU - Armon, Amitai
AU - Azar, Yossi
AU - Epstein, Leah
AU - Regev, Oded
PY - 2002
Y1 - 2002
N2 - Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin El-Yaniv]. We resolve this problem by providing an unapproximability 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 unapproximability for the general case.
AB - Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin El-Yaniv]. We resolve this problem by providing an unapproximability 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 unapproximability for the general case.
UR - http://www.scopus.com/inward/record.url?scp=2442537301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2442537301&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:2442537301
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 116
EP - 124
BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PB - Association for Computing Machinery
T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Y2 - 6 January 2002 through 8 January 2002
ER -