An improved approximation algorithm for RESOURCE ALLOCATION

摘要

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