3 papers
cs.DS2016
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…
cs.DS2015
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…
cs.DM2011
On the gap between ess(f) and cnf_size(f)
Lisa Hellerstein, Devorah Kletenik
Given a Boolean function f, the quantity ess(f) denotes the largest set of assignments that falsify f, no two of which falsify a common implicate of f. Although ess(f)$ is clearly…