An Improved Approximation Algorithm for RESOURCE ALLOCATION

被引：26

作者：

Calinescu, Gruia ^{[1
]}

Chakrabarti, Amit ^{[2
]}

Karloff, Howard ^{[3
]}

Rabani, Yuval ^{[4
]}

机构：

[1] IIT, Dept Comp Sci, Chicago, IL 60616 USA

[2] Dartmouth Coll, Dept Comp Sci, Hanover, NH 03755 USA

[3] AT&T Labs Res, Florham Pk, NJ 07932 USA

[4] Hebrew Univ Jerusalem, Dept Comp Sci, IL-91904 Jerusalem, Israel

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2011年 / 7卷 / 04期

基金：

以色列科学基金会;

关键词：

Approximation algorithm; resource allocation; call admission control; BANDWIDTH;

D O I：

10.1145/2000807.2000816

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 - epsilon)-approximated in randomized polynomial time, which improves upon earlier approximation results.

引用

页数：7

共 9 条

[1] SCHEDULING JOBS WITH FIXED START AND END TIMES [J].

ARKIN, EM ;

SILVERBERG, EB .

DISCRETE APPLIED MATHEMATICS, 1987, 18 (01) :1-8

[2] A unified approach to approximating resource allocation and scheduling [J].

Bar-Noy, A ;

Bar-Yehuda, R ;

Freund, A ;

Naor, J ;

Schieber, B .

JOURNAL OF THE ACM, 2001, 48 (05) :1069-1090

[3]

Calinescu G., 2002, Integer Programming and Combinatorial Optimization. 9th International IPCO Conference Proceedings (Lecture Notes in Computer Science Vol.2337), P401

[4]

Chen B, 2002, IIE TRANS, V34, P501, DOI 10.1023/A:1013535723204

[5] MAXIMIZING THE VALUE OF A SPACE MISSION [J].

HALL, NG ;

MAGAZINE, MJ .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 78 (02) :224-241

[6]

Leonardi S, 2000, LECT NOTES COMPUT SC, V1974, P409

[7] A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM [J].

ORLIN, JB .

OPERATIONS RESEARCH, 1993, 41 (02) :338-350

[8]

PHILLIPS C. A., 2000, J SCHEDULING, V3, P365, DOI DOI 10.1002/1099-1425(200011/12)3:6<365::AID-JOS56>3.0.CO

[9]

2-P

← 1 →