On-line restricted assignment of temporary tasks with unknown durations

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

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 Ω(m2/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.

Original languageEnglish (US)
Pages (from-to)67-72
Number of pages6
JournalInformation Processing Letters
Volume85
Issue number2
DOIs
StatePublished - Jan 31 2003

Keywords

  • Competitiveness
  • On-line algorithms
  • Temporary tasks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'On-line restricted assignment of temporary tasks with unknown durations'. Together they form a unique fingerprint.

Cite this