Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143016 | Operations Research Letters | 2010 | 4 Pages |
Abstract
We consider a stochastic knapsack problem where each item has a known profit but a random size that is normally distributed independent of other items. The goal is to select a profit maximizing set of items such that the probability of the total size exceeding the knapsack bound is at most a given threshold. We present a Polynomial Time Approximation Scheme (PTAS) for the problem via a parametric LP reformulation that efficiently computes a solution satisfying the chance constraint strictly and achieving near-optimal profit.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vineet Goyal, R. Ravi,