Simultaneous selection

详细信息    查看全文

• 作者：Wojciech Olszewski^a ; ^{wo@northwestern.edu" class="auth_mail" title="E-mail the corresponding author} ; Rakesh Vohra^b ; ^{rvohra@seas.upenn.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Submodularity ; Greedy ; Selection
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：161-169
• 全文大小：382 K

文摘

We generalize Chade and Smith’s (2006) simultaneous search problem to a class of discrete optimization problems. More precisely, we study the problem of maximizing a weighted sum of utilities of objects minus the sum of costs of acquiring these objects, given the constraint that the sum of weights cannot exceed the value of some submodular function.

We show that the problem has a simple solutions in the particular case in which the submodular function depends only on the number of objects. Namely, the optimal set of objects can be found by the greedy algorithm. We provide some economic applications of this result. The particular case studied in the present paper, and the particular case studied by Chade and Smith complement one another, but they do not exhaust all instances of our general discrete optimization problem. We also show that in the general case the problem does not have a simple solution.