A Tight Bound for Stochastic Submodular Cover

Abstract

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′<Q. 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. The subsequent corrected proof of Golovin and Krause gives a quadratic bound of (ln(Q/η)+1). A bound of 56(ln(Q/η)+1) is implied by work of Im et al. Other bounds for the problem depend on quantities other than Q and η. Our bound restores the original bound claimed by Golovin and Krause, generalizing 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.