Evaluation of monotone DNF formulas

DOI10.1007/S00453-015-0092-9zbMATH Open1364.68221arXiv1310.3673OpenAlexW2174148654MaRDI QIDQ521804FDOQ521804

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

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Simple algorithms for stochastic score classification with small approximation ratios
• Title not available (Why is that?)
• 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
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Submodular goal value of Boolean functions
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Sequential testing in batches
• 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)