# A Tight Bound for Stochastic Submodular Cover

arXiv: https://arxiv.org/abs/2102.01149 · HTML: https://mlsanity.com/paper/2102.01149/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 18 references that are in the map.
- First posted on arXiv 1 Feb 2021.

## Builds on (most cited first, 1 of 1)

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)

## Built on by (most cited first, 4 of 4)

- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Minimum Cost Adaptive Submodular Cover](https://mlsanity.com/paper/2208.08351/) (2022)
- [Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover](https://mlsanity.com/paper/2405.14995/) (2024)
- [Cost-Aware Recovery-Pathway Identification and Bayesian Optimization for Autonomous Materials Discovery](https://mlsanity.com/paper/2607.23896/) (2026)

## Abstract (arXiv)

We show that the Adaptive Greedy algorithm of Golovin and Krause (2011) achieves an approximation bound of (ln (Q/η)+1) for Stochastic Submodular Cover: here Q is the "goal value" and η is the smallest non-zero marginal increase in utility deliverable by an item. (For integer-valued utility functions, we show a bound of H(Q), where H(Q) is the Qth Harmonic number.) Although this bound was claimed by Golovin and Krause in the original version of their paper, the proof was later shown to be incorrect by Nan and Saligrama (2017). The subsequent corrected proof of Golovin and Krause (2017) gives a quadratic bound of (ln(Q/η) + 1)2. Other previous bounds for the problem are 56(ln(Q/η) + 1), implied by work of Im et al. (2016) on a related problem, and k(ln (Q/η)+1), due to Deshpande et al. (2016) and Hellerstein and Kletenik (2018), where k is the number of states. Our bound generalizes the well-known (ln~m + 1) approximation bound on the greedy algorithm for the classical Set Cover problem, where m is the size of the ground set.