کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1142212 957137 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximizing expected utility over a knapsack constraint
ترجمه فارسی عنوان
حداکثر استفاده از ابزار مورد انتظار در یک محدودیت کوله پشتی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The expected utility knapsack problem is to pick a set of items with random values so as to maximize the expected utility of the total value of the items picked subject to a knapsack constraint. We devise an approximation algorithm for this problem by combining sample average approximation and greedy submodular maximization. Our main result is an algorithm that maximizes an increasing submodular function over a knapsack constraint with an approximation ratio better than the well known (1−1/e1−1/e) factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 44, Issue 2, March 2016, Pages 180–185
نویسندگان
, ,