Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

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, 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). 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 non-adaptive policy whose expected value approximates that of an optimal adaptive policy to within a factor of 4. We also devise a polynomial-time adaptive policy that approximates the optimal adaptive policy to within a factor of 3 + ε for any constant ε> 0