This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Dean, B. C. Articles by Vondrák, J. Search for Related Content

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

School of Computing, McAdams Hall, Clemson, South Carolina 29634
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Department of Mathematics, Princeton University, Princeton, New Jersey 08544
bcdean{at}cs.clemson.edu
goemans{at}math.mit.edu
jvondrak{at}gmail.com

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 successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both nonadaptive 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). An important facet of our work lies in characterizing the benefit of adaptivity. For this purpose we advocate the use of a measure called the adaptivity gap: the ratio of the expected value obtained by an optimal adaptive policy to that obtained by an optimal nonadaptive policy. We bound the adaptivity gap of the stochastic knapsack problem by demonstrating a polynomial-time algorithm that computes a nonadaptive policy whose expected value approximates that of an optimal adaptive policy to within a factor of four. We also devise a polynomial-time adaptive policy that approximates the optimal adaptive policy to within a factor of 3 + for any constant > 0.

Key Words: knapsack problem; stochastic models; approximation algorithm; adaptivity
History: Received: May 23, 2005; revision received: March 27, 2008;

This article has been cited by other articles:

				N. Halman, D. Klabjan, M. Mostagir, J. Orlin, and D. Simchi-Levi A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand Mathematics of Operations Research, August 1, 2009; 34(3): 674 - 685. [Abstract] [PDF]