@inproceedings{8985c4fb50fc4966abfb2709af33a311,
title = "A unified approach to approximating resource allocation and scheduling",
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.",
keywords = "bandwidth allocation, interval graphs, interval scheduling, resource allocation, scheduling, scheduling with release times and deadlines",
author = "Amotz Bar-Noy and Reuven Bar-Yehuda and Ari Freund and Joseph Naor and Baruch Schieber",
year = "2000",
doi = "10.1145/335305.335410",
language = "English (US)",
isbn = "1581131844",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "735--744",
booktitle = "Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000",
note = "32nd Annual ACM Symposium on Theory of Computing, STOC 2000 ; Conference date: 21-05-2000 Through 23-05-2000",
}