Evaluation of monotone DNF formulas

DOI10.1007/S00453-015-0092-9MaRDI QIDQ521804zbMATH OpenOpenAlexFDO

Authors Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, Tonguç Ünlüyurt

Publication date 12 April 2017

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmssequential testingDNF formulasstochastic Boolean function evaluation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25)

Abstract: Stochastic Boolean Function Evaluation (SBFE) 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 a given associated cost $c_i$. Further, $x$ is drawn from a given product distribution: for each $x_i$, $Prob[x_i=1]=p_i$, and the bits are independent. The goal is to minimize the expected cost of evaluation. Stochastic Boolean Function Evaluation (SBFE) 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 a given associated cost $c_i$. Further, $x$ is drawn from a given product distribution: for each $x_i$, $Prob[x_i=1]=p_i$, and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

Recommendations

• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS
• Function Evaluation Via Linear Programming in the Priced Information Model
• Submodular goal value of Boolean functions

Cites work

• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1098497 (Why is no real title available?)
• scientific article; zbMATH DE number 1983159 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A note on the generalized min-sum set cover problem
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Database Theory - ICDT 2005
• Exact learning when irrelevant variables abound
• Finding optimal satisficing strategies for and-or trees
• Group-Based Active Query Selection for Rapid Diagnosis in Time-Critical Situations
• Heuristic least-cost computation of discrete classification functions with uncertain argument values
• Learning with attribute costs
• On chromatic sums and distributed resource allocation
• On the competitive ratio of evaluating priced functions
• Query strategies for priced information
• Sequential testing of complex systems: a review

Cited in

(11)

• Simple algorithms for stochastic score classification with small approximation ratios
• scientific article; zbMATH DE number 7378706 (Why is no real title available?)
• A polynomial-time approximation scheme for sequential batch testing of series systems
• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• The stochastic Boolean function evaluation problem for symmetric Boolean functions
• Mathematical Foundations of Computer Science 2005
• Submodular goal value of Boolean functions
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Sequential testing in batches
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Non-adaptive stochastic score classification and explainable halfspace evaluation

This page was built for publication: Evaluation of monotone DNF formulas

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