Abstract
We study the problem of finding a most profitable subset of n given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity B of available resource. We show that this NP-hard Resource Allocation problem can be (1/2 - ε)-approximated in polynomial time, which improves upon earlier approximation results for this problem, the best previously published result being a 1/4-approximation. We also give a simpler and faster 1/3-approximation algorithm.
Part of this work was done while visiting AT&T Labs - Research. Work at Princeton University supported by NSF Grant CCR-99817 and ARO Grant DAAH04-96-1-0181.
Part of this work was done while visiting AT&T Labs - Research. Work at the Technion supported by Israel Science Foundation grant number 386/99, by BSF grants 96-00402 and 99-00217, by Ministry of Science contract number 9480198, by EU contract number 14084 (APPOL), by the CONSIST consortium (through the MAGNET program of the Ministry of Trade and Industry), and by the Fund for the Promotion of Research at the Technion.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. M. Arkin, E. B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18 (1987), 1–8.
A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, B. Schieber. A unified approach to approximating resource allocation and scheduling. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000), 735–744.
A. Bar-Noy. Private communication (2001).
B. Chen, R. Hassin, M. Tzur. Allocation of bandwidth and storage. IIE Transactions, 34 (2002), 501–507.
N. G. Hall, M. J. Magazine. Maximizing the value of a space mission. European Journal of Operational Research, 78 (1994), 224–241.
S. Leonardi, A. Marchetti-Spaccamela, A. Vitaletti. Approximation algorithms for bandwidth and storage allocation problems under real time constraints. In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (2000), 409–420.
J. B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41 (1993), 338–350.
C. Phillips, R N. Uma, J. Wein. Off-line admission control for general scheduling problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000), 879–888.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y. (2002). Improved Approximation Algorithms for Resource Allocation. In: Cook, W.J., Schulz, A.S. (eds) Integer Programming and Combinatorial Optimization. IPCO 2002. Lecture Notes in Computer Science, vol 2337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47867-1_28
Download citation
DOI: https://doi.org/10.1007/3-540-47867-1_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43676-8
Online ISBN: 978-3-540-47867-6
eBook Packages: Springer Book Archive