Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline

Lisa Hellerstein, Devorah Kletenik, Patrick Lin

We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offl…