Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2000807.2000816 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
resource allocation,quantity b,approximation result,resource requirement,improved approximation algorithm,available resource,np-hard resource allocation problem,randomized polynomial time,profitable subset,approximation algorithm,profitability | Approximation algorithm,Mathematical optimization,Computer science,Call Admission Control,Resource allocation,Time complexity | Journal |
Volume | Issue | ISSN |
7 | 4 | 1549-6325 |
Citations | PageRank | References |
8 | 0.53 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gruia Calinescu | 1 | 1487 | 94.99 |
| Amit Chakrabarti | 2 | 714 | 38.18 |
| Howard Karloff | 3 | 1673 | 195.13 |
| Yuval Rabani | 4 | 2265 | 274.98 |