Approximating the stochastic knapsack problem:: The benefit of adaptivity

被引:80
作者
Dean, BC [1 ]
Goemans, MX [1 ]
Vondrák, J [1 ]
机构
[1] MIT, CSAIL, Cambridge, MA 02139 USA
来源
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2004年
关键词
D O I
10.1109/FOCS.2004.15
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution "policy" that maximizes the expected value of items placed in the knapsack, and we consider both non-adaptive policies (that designate a priori a fixed sequence of items to insert) and adaptive policies (that can make dynamic choices based on the instantiated sizes of items placed in the knapsack thus far). We show that adaptivity provides only a constant-factor improvement by demonstrating a greedy non-adaptive algorithm that approximates the optimal adaptive policy within a factor of 7. We also design an adaptive polynomial-time algorithm which approximates the optimal adaptive policy within a factor of 5 + epsilon, for any constant epsilon > 0.
引用
收藏
页码:208 / 217
页数:10
相关论文
共 14 条
[1]  
[Anonymous], 1966, MANAGEMENT SCI
[2]  
[Anonymous], 1997, P 20 9 ANN ACM S THE
[3]   ARTHUR-MERLIN GAMES - A RANDOMIZED PROOF SYSTEM, AND A HIERARCHY OF COMPLEXITY CLASSES [J].
BABAI, L ;
MORAN, S .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (02) :254-276
[4]  
Birge J. R., 1997, INTRO STOCHASTIC PRO
[5]   AN ALGORITHM FOR MAXIMIZING TARGET ACHIEVEMENT IN THE STOCHASTIC KNAPSACK-PROBLEM WITH NORMAL RETURNS [J].
CARRAWAY, RL ;
SCHMIDT, RL ;
WEATHERFORD, LR .
NAVAL RESEARCH LOGISTICS, 1993, 40 (02) :161-173
[6]   Random debaters and the hardness of approximating stochastic functions [J].
Condon, A ;
Feigenbaum, J ;
Lund, C ;
Shor, P .
SIAM JOURNAL ON COMPUTING, 1997, 26 (02) :369-400
[7]   RENEWAL DECISION PROBLEM [J].
DERMAN, C ;
LIEBERMAN, GJ ;
ROSS, SM .
MANAGEMENT SCIENCE, 1978, 24 (05) :554-561
[8]  
Goel A., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P579, DOI 10.1109/SFFCS.1999.814632
[9]   RISK CRITERIA IN A STOCHASTIC KNAPSACK-PROBLEM [J].
HENIG, MI .
OPERATIONS RESEARCH, 1990, 38 (05) :820-825
[10]  
IMMORLICA N, 2004, SODA, P184