TY - JOUR

T1 - A tight bound for stochastic submodular cover

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

AU - Parthasarathy, Srinivasan

N1 - Funding Information:
Partial support for this work came from NSF Award IIS-1909335 (for L. Hellerstein) and from a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York (for D. Kletenik). We thank the anonymous referees for their comprehensive and useful comments. We thank Naifeng Liu for proofreading help.
Publisher Copyright:
© 2021 AI Access Foundation. All rights reserved.

PY - 2021

Y1 - 2021

N2 - 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 Q0<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)2. 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.

AB - 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 Q0<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)2. 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.

UR - http://www.scopus.com/inward/record.url?scp=85108809561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108809561&partnerID=8YFLogxK

U2 - 10.1613/jair.1.12368

DO - 10.1613/jair.1.12368

M3 - Article

AN - SCOPUS:85108809561

VL - 71

SP - 347

EP - 370

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -