A Tight Bound for Stochastic Submodular Cover
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy · Journal of Artificial Intelligence Research · 2021
We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q'