A unified approach to approximating resource allocation and scheduling.

A unified approach to approximating resource allocation and scheduling.

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-...

Disgrifiad llawn

Manylion Llyfryddiaeth
Cyhoeddwyd yn:Journal of the ACM 48, 5 (2001).
Prif Awdur: Bar-Noy, Amotz
Fformat: Erthygl
Iaith:English
Pynciau:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Computations on discrete structures.
Sequencing and scheduling.
Algorithms.
Performance.