# Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

arXiv: https://arxiv.org/abs/1303.0726 · HTML: https://mlsanity.com/paper/1303.0726/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2013.

## Built on by (most cited first, 10 of 10)

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [All models are wrong, some are useful: Model Selection with Limited Labels](https://mlsanity.com/paper/2410.13609/) (2024)
- [USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems](https://mlsanity.com/paper/2107.07508/) (2021)
- [Regularized impurity reduction: Accurate decision trees with complexity guarantees](https://mlsanity.com/paper/2208.10949/) (2022)
- [Limited Query Graph Connectivity Test](https://mlsanity.com/paper/2302.13036/) (2023)
- [EarthSight: A Distributed Framework for Low-Latency Satellite Intelligence](https://mlsanity.com/paper/2511.10834/) (2025)
- [Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory](https://mlsanity.com/paper/2505.01028/) (2025)
- [Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation](https://mlsanity.com/paper/2606.24672/) (2026)
- [How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction](https://mlsanity.com/paper/2609.18622/) (2026)
- [Drafting Agents, Not Just Tokens: Speculative Recursive Self-Improvement for Agentic Systems](https://mlsanity.com/paper/2610.16491/) (2026)

## Abstract (arXiv)

Stochastic Boolean Function Evaluation is the problem of determining the value of a given Boolean function f on an unknown input x, when each bit of x_i of x can only be determined by paying an associated cost c_i. The assumption is that x is drawn from a given product distribution, and the goal is to minimize the expected cost. This problem has been studied in Operations Research, where it is known as "sequential testing" of Boolean functions. It has also been studied in learning theory in the context of learning with attribute costs. We consider the general problem of developing approximation algorithms for Stochastic Boolean Function Evaluation. We give a 3-approximation algorithm for evaluating Boolean linear threshold formulas. We also present an approximation algorithm for evaluating CDNF formulas (and decision trees) achieving a factor of O(log kd), where k is the number of terms in the DNF formula, and d is the number of clauses in the CNF formula. In addition, we present approximation algorithms for simultaneous evaluation of linear threshold functions, and for ranking of linear functions. Our function evaluation algorithms are based on reductions to the Stochastic Submodular Set Cover (SSSC) problem. This problem was introduced by Golovin and Krause. They presented an approximation algorithm for the problem, called Adaptive Greedy. Our main technical contribution is a new approximation algorithm for the SSSC problem, which we call Adaptive Dual Greedy. It is an extension of the Dual Greedy algorithm for Submodular Set Cover due to Fujito, which is a generalization of Hochbaum's algorithm for the classical Set Cover Problem. We also give a new bound on the approximation achieved by the Adaptive Greedy algorithm of Golovin and Krause.