Temporary tasks assignment resolved

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev

Research output: Contribution to journalArticlepeer-review


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, see [12]. 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.

Original languageEnglish (US)
Pages (from-to)295-314
Number of pages20
JournalAlgorithmica (New York)
Issue number3
StatePublished - Jul 2003


  • Competitive
  • Load balancing
  • On-line
  • PTAS
  • Unrelated machines

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Temporary tasks assignment resolved'. Together they form a unique fingerprint.

Cite this