A unified approach to approximating resource allocation and scheduling

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

51 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; (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. They use the local-ratio technique and can be equivalently interpreted within the primal-dual schema.

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Pages735-744
Number of pages10
DOIs
StatePublished - 2000
Externally publishedYes
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/TerritoryUnited States
CityPortland, OR
Period5/21/005/23/00

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • bandwidth allocation
  • interval graphs
  • interval scheduling
  • resource allocation
  • scheduling
  • scheduling with release times and deadlines

Fingerprint

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

Cite this