1.1k citations
- City University of New YorkUS76 papers
- The Graduate Center, CUNYUS50 papers
- New York UniversityUS8 papers
- New York City College of TechnologyUS5 papers
- Centre National de la Recherche ScientifiqueFR4 papers
- Imperial College LondonGB4 papers
- Lehman CollegeUS4 papers
- Princeton UniversityUS4 papers
- College of Staten IslandUS3 papers
- Columbia UniversityUS3 papers
- State University of New YorkUS3 papers
- Trinity College DublinIE3 papers
Showing 2021 · cs.DSShow all
2 papers · 2 filters
cs.DS2021★ 4 cited
The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein +1
We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an -approximation al…
cs.DS2021★ 3 cited
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…