4 papers · 1 filter
A Tight Bound for Stochastic Submodular Cover
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy
We show that the Adaptive Greedy algorithm of Golovin and Krause (2011) achieves an approximation bound of for Stochastic Submodular Cover: here is the "goal va…
The Stochastic Score Classification Problem
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein +1
Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform tests on the patient. Ea…
Scenario Submodular Cover
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik +1
Many problems in Machine Learning can be modeled as submodular optimization problems. Recent work has focused on stochastic or adaptive versions of these problems. We consider the…
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…