Prefer a chat interface with context about you and your work?
A Tight Bound for Stochastic Submodular Cover

 
 
 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 …