A tight bound for stochastic submodular cover

Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy

    Research output: Contribution to journalArticlepeer-review

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

    Original languageEnglish (US)
    Pages (from-to)347-370
    Number of pages24
    JournalJournal of Artificial Intelligence Research
    Volume71
    DOIs
    StatePublished - 2021

    ASJC Scopus subject areas

    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'A tight bound for stochastic submodular cover'. Together they form a unique fingerprint.

    Cite this