Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack

Amol Deshpande, Lisa Hellerstein, Devorah Kletenik

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We present a new approximation algorithm for the stochastic submodular set cover (SSSC) problem called adaptive dual greedy. We use this algorithm to obtain a 3-approximation algorithm solving the stochastic Boolean function evaluation (SBFE) problem for linear threshold formulas (LTFs). We also obtain a 3- approximation algorithm for the closely related stochastic min-knapsack problem and a 2-approximation for a variant of that problem. We prove a new approximation bound for a previous algorithm for the SSSC problem, the adaptive greedy algorithm of Golovin and Krause. We also consider an approach to approximating SBFE problems using the adaptive greedy algorithm,which we call the Q-value approach. This approach easily yields a new result for evaluation of CDNF (conjunctive / disjunctive normal form) formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q-value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for LTFs or read-once disjunctive normal form formulas.

    Original languageEnglish (US)
    Article number42
    JournalACM Transactions on Algorithms
    Volume12
    Issue number3
    DOIs
    StatePublished - Apr 2016

    Keywords

    • Boolean function evaluation
    • Sequential testing

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)

    Fingerprint Dive into the research topics of 'Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack'. Together they form a unique fingerprint.

    Cite this