کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1143016 | 957173 | 2010 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A PTAS for the chance-constrained knapsack problem with random item sizes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 3, May 2010, Pages 161–164
Journal: Operations Research Letters - Volume 38, Issue 3, May 2010, Pages 161–164
نویسندگان
Vineet Goyal, R. Ravi,