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
SN - 1076-9757
VL - 71
SP - 347
EP - 370
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -