Stochastic Knapsack without Relaxing the Capacity

We present the first polynomial-time approximation scheme (PTAS) for the stochastic knapsack problem that does not relax the knapsack’s capacity. Given n items with known arbitrary independent size distributions and fixed profits, an accuracy parameter $\varepsilon \in(0,1)$, and an overflow probability bound $\alpha$, our algorithm computes a set of items with profit at least $(1-\varepsilon)$ times optimal, while ensuring the probability of exceeding the capacity is at most $4 \sqrt{\alpha}+\varepsilon$. Prior to our work, no PTAS was known without either allowing a ($1+\varepsilon$) capacity expansion or restricting to special distribution classes (such as Poisson or Gaussian). A key tool in our algorithm is an anti-concentration result that allows us to handle “low-profit” items by adapting a known PTAS result for the case when we are allowed to expand knapsack capacity by a ($1+\varepsilon$) factor. We then show that we are able to convert this solution into another solution with a similar profit which strictly obeys the knapsack capacity, but requires that we relax the overflow probability to a $4 \sqrt{\alpha}+\varepsilon$ factor. In the special case where the item sizes are scaled Bernoulli random variables (which have support on 0 and exactly one other value), we extend our approach to obtain an improved overflow probability guarantee of $\alpha+\varepsilon$. We make this improvement by exploiting the fact that these random variables are defined by only two parameters (the probability of being non-zero and the non-zero value in the support), which allows us to avoid some of the complexity and overhead of our algorithm for arbitrary distributions.