Adaptivity in the stochastic blackjack knapsack problem

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. In every stage of insertion if the subset of the items inserted thus far is feasible, then it has a total value that equals to the sum of values of all items of this subset. Otherwise, if the subset violates the constraint, then its value equals to zero. The goal is to compute a policy for insertion of the items, that maximizes the expected total value of items placed in the knapsack.We consider both non-adaptive policies (that designate a priori a fixed subset of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. First we show a tight bound of 32 on the adaptivity gap for the case of inputs consisting of only two items. Then we present a non-adaptive policy with expected value that is at least (2−1)2/2≈1/11.66 times the expected value of the optimal adaptive policy. Thus the adaptivity gap in this model is at most 11.66. Additionally this non-adaptive policy is computed in polynomial time. Finally, we consider a special case of the model where all sizes are distributed according to Bernoulli distribution with different parameters. For this special case we improve our result and bound the adaptivity gap by 8.