New Bounds for the Stochastic Knapsack Problem

The knapsack problem is a problem in combinatorial optimization that seeks to maximize the objective function \(\sum_{i = 1}^{n} v_ix_i\) subject to the constraints \(\sum_{i = 1}^{n} w_ix_i \leq W\) and \(x_i \in \{0, 1\}\), where \(\mathbf{x}, \mathbf{v} \in \mathbb{R}^{n}\) and \(W\) are provided. We consider the stochastic variant of this problem in which \(\mathbf{v}\) remains deterministic, but \(\mathbf{x}\)is an \(n\)-dimensional vector drawn uniformly at random from \([0, 1]^{n}\). We establish a sufficient condition under which the summation-bound condition is almost surely satisfied. Furthermore, we discuss the implications of this result on the deterministic problem.