A unified approach to approximating resource allocation and scheduling

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

249 Scopus citations

Abstract

We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.

Original languageEnglish (US)
Pages (from-to)1069-1090
Number of pages22
JournalJournal of the ACM
Volume48
Issue number5
DOIs
StatePublished - Sep 1 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Approximation algorithms for NP-hard problems
  • Dynamic storage allocation
  • General caching
  • Resource allocation
  • Scheduling

Fingerprint Dive into the research topics of 'A unified approach to approximating resource allocation and scheduling'. Together they form a unique fingerprint.

Cite this