Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximation Algorithms for Stochastic Boolean Function Evaluation and
  Stochastic Submodular Set Cover   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.

28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
16
The categories of this paper are: stat
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
5
The categories of this paper are: gr-qc
2
The categories of this paper are: math
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
36
The categories of this paper are: cmp-lg
13
The categories of this paper are: quant-ph
15
The categories of this paper are: nucl-ex