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 $(\ln (Q/\eta )+1)$ for Stochastic Submodular Cover: here $Q$ is the "goal va…