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

DOI10.1137/1.9781611973402.107MaRDI QIDQ5384069zbMATH OpenOpenAlexFDO

Authors Amol Deshpande, Devorah Kletenik, Lisa Hellerstein

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.0726

Mathematics Subject Classification ID

Approximation algorithms (68W25) Stochastic programming (90C15) Combinatorial optimization (90C27)

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

Recommendations

• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Scenario submodular cover
• Evaluation of monotone DNF formulas
• A Tight Bound for Stochastic Submodular Cover
• Stochastic submodular cover with limited adaptivity

Cited in

(16)

• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• The stochastic Boolean function evaluation problem for symmetric Boolean functions
• Decision tree classification with bounded number of errors
• Sequential testing in batches
• Scenario submodular cover
• Totally optimal decision trees for Boolean functions
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Revisiting the approximation bound for stochastic submodular cover
• A Tight Bound for Stochastic Submodular Cover
• A polynomial-time approximation scheme for sequential batch testing of series systems
• Max-throughput for (conservative) k-of-n testing
• Evaluation of monotone DNF formulas
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Approximation algorithm for fair stochastic maximum coverage problem
• An algorithm for bichromatic sorting with polylog competitive ratio
• On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting

This page was built for publication: Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384069)