## Chance Constrained Knapsack Problem with Random Item Sizes

journal contribution

posted on 01.01.2008 by Vineet Goyal, Ramamoorthi Ravi#### journal contribution

Any type of content formally published in an academic journal, usually following a peer-review process.

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.