Maximizing Stochastic Monotone Submodular Functions

Arash Asadpour () and Hamid Nazerzadeh ()
Additional contact information
Arash Asadpour: Stern School of Business, New York University, New York, New York 10012
Hamid Nazerzadeh: Marshall School of Business, University of Southern California, Los Angeles, California 90089

Management Science, 2016, vol. 62, issue 8, 2374-2391

Abstract: We study the problem of maximizing a stochastic monotone submodular function with respect to a matroid constraint. Because of the presence of diminishing marginal values in real-world problems, our model can capture the effect of stochasticity in a wide range of applications. We show that the adaptivity gap—the ratio between the values of optimal adaptive and optimal nonadaptive policies—is bounded and is equal to e /( e − 1). We propose a polynomial-time nonadaptive policy that achieves this bound. We also present an adaptive myopic policy that obtains at least half of the optimal value. Furthermore, when the matroid is uniform, the myopic policy achieves the optimal approximation ratio of 1 − 1/ e . This paper was accepted by Dimitris Bertsimas and Yinyu Ye, optimization .

Keywords: submodular maximization; stochastic optimization; adaptivity gap; influence spread in social networks (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2015.2254 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:62:y:2016:i:8:p:2374-2391

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().