Approximation algorithms for stochastic boolean function evaluation and stochastic submodular set cover

Amol Deshpande, Lisa Hellerstein, Devorah Kletenik

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We present approximation algorithms for two problems: Stochastic Boolean Function Evaluation (SBFE) and Stochastic Submodular Set Cover (SSSC). Our results for SBFE problems are obtained by reducing them to SSSC problems through the construction of appropriate utility functions. We give a new algorithm for the SSSC problem that we call Adaptive Dual Greedy. We use this algorithm to obtain a 3-approximation algorithm solving the SBFE problem for linear threshold formulas. We also get a 3-approximation algorithm for the closely related Stochastic Min-Knapsack problem, and a 2-approximation for a natural special case of that problem. In addition, we prove a new approximation bound for a previous algorithm for the SSSC problem, Adaptive Greedy. We consider an approach to approximating SBFE problems using existing techniques, which we call the Q-value approach. This approach easily yields a new result for evaluation of CDNF 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 linear threshold formulas or read-once DNF.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    PublisherAssociation for Computing Machinery
    Pages1453-1467
    Number of pages15
    ISBN (Print)9781611973389
    DOIs
    StatePublished - 2014
    Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
    Duration: Jan 5 2014Jan 7 2014

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
    CountryUnited States
    CityPortland, OR
    Period1/5/141/7/14

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

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

  • Cite this

    Deshpande, A., Hellerstein, L., & Kletenik, D. (2014). Approximation algorithms for stochastic boolean function evaluation and stochastic submodular set cover. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 (pp. 1453-1467). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973402.107