Technical Report CS0968

Title: A Unified Approach to Approximating Resource Allocation and Scheduling
Authors: Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber
Abstract: This paper addresses a general framework for 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 prominent problems among others: (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 many of the problems, this is the first constant factor approximation algorithm. Our algorithms are extremely simple and efficient. They use the local-ratio technique but they can also be equivalently interpreted within the primal-dual schema.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion