Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack

作者：Deshpande Amol^*; Hellerstein Lisa; Kletenik Devorah

来源：ACM Transactions on Algorithms, 2016, 12(3): 42.

DOI：10.1145/2876506

• Sequential testing
• Boolean function evaluation

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.

• 出版日期2016-6