Title: Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack,
Abstract: 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 overflow probability). While
several approximation algorithms 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 overflow 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. (iii) Our third result
is in the case when item sizes are so-called "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.
Crucially, all of our algorithms meet the capacity constraint exactly, a
result which was previously known only when the item sizes were Poisson or
Gaussian random variables. Our results rely on new connections between Boolean
function analysis and stochastic optimization. We believe that these ideas and
techniques may prove to be useful in other stochastic optimization problems as
well.