Chance Constrained Knapsack Problem with Random Item Sizes

We consider a stochastic knapsack problem where each item has a known profit but a random size. The goal is to select a profit maximizing set of items such that the probability of the total size of selected items exceeding the knapsack size is at most a given threshold. This problem finds applications in capital investment problems where a set of projects needs to be selected from the available pool of projects to invest a given amount of capital. The investment requirement for each project is typically uncertain in the selection phase and is known only after it has been selected and started. We present an FPTAS for the case when each item size is normally distributed and independent of other items. We present a parametric LP formulation and show that it is a good approximation of the chance-constrained stochastic knapsack problem. Furthermore, we give a polynomial time algorithm to round any fractional solution of the parametric LP to obtain an integral solution whose profit is within (1 + ∈)-factor of the objective value of the fractional solution for any ∈ > 0.