Adaptivity in the stochastic covering knapsack problem
The covering knapsack problem is the following problem. The input consists of a set of items each of which is associated with a non-negative cost and a non-negative size, and the goal is to find a minimum-cost subset of these items whose total size is at least 1. In our stochastic model the costs are deterministic while the sizes are random variables with known, arbitrary distributions and these random variables are mutually independent. The goal is to compute a policy that minimizes the expected cost of items covering the total size of 1, where the first item to overflow the knapsack terminates the process of selecting items. Once an item is placed in the knapsack, the realization of its size is revealed (and is not changed later).
An adaptive policy which decides upon the next action according to the realizations of the random variables which became known in previous stages of the optimization procedure while a non-adaptive policy is a permutation of the items. We examine the adaptivity gap, i.e., the supremum ratio between the expected cost of an optimal non-adaptive policy and the expected cost of an optimal adaptive policy.