Maximizing expected utility over a knapsack constraint

详细信息    查看全文

• 作者：Jiajin Yu^a ; ^{jiajinyu@gatech.edu" class="auth_mail" title="E-mail the corresponding author} ; Shabbir Ahmed^b ; ^{sahmed@isye.gatech.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Knapsack problem ; Utility maximization ; Submodularity ; Sample average approximation ; Approximation algorithm
• 刊名：Operations Research Letters
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：44
• 期：2
• 页码：180-185
• 全文大小：382 K

文摘

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/e$1-1/e$) factor.