Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack

The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasiFPTAS. (iii) Our third result is in the case when item sizes are socalled "hypercontractive" random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overow probability and maximum profit.