An improved approximation algorithm for resource allocation
Gruiă Cälinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani · ACM Transactions on Algorithms · 2011
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 randomized polynomial time, which improves upon earlier approximation results.