Maximizing Stochastic Monotone Submodular Functions
研究了在拟阵约束下最大化随机单调子模函数的问题，证明了自适应差距有界且等于e/(e-1)，并提出了多项式时间的非自适应策略达到该界，以及自适应短视策略获得至少一半的最优值。
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.