Simultaneous selection

Wojciech Olszewski*, Rakesh Vohra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)161-169
Number of pages9
JournalDiscrete Applied Mathematics
Volume200
DOIs
StatePublished - Feb 19 2016

Keywords

  • Greedy
  • Selection
  • Submodularity

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Simultaneous selection'. Together they form a unique fingerprint.

Cite this