An improved approximation algorithm for resource allocation
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 randomized polynomial time, which improves upon earlier approximation results.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 01, 2011
- Source ID
- 10.1145/2000807.2000816
Entities
People
- Amit Chakrabarti
- Gruia Calinescu
- Howard Karloff
- Yuval Rabani
Organizations
- Army Research Office
- Bulgarian Science Fund
- Dartmouth College
- EU Business School
- Hebrew University of Jerusalem
- Illinois Institute of Technology
- Israel Science Foundation
- National Science Foundation