Maximizing Stochastic Monotone Submodular Functions

• 成果类型: Article
• 署名作者: Asadpour, Arash; Nazerzadeh, Hamid
• 署名单位: New York University; University of Southern California
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2015.2254
• 发表日期: 2016
• 页码: 2374-2391
• 关键词: submodular maximization; stochastic optimization; adaptivity gap; influence spread in social networks

摘要

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.