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 & 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.