Competitive evaluation of threshold functions in the priced information model

In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 2002) the authors proposed a new model for studying the function evaluation problem based on a variant of the classical decision tree problem for Boolean functions. In this variant each variable of the function to evaluate has an associated cost which has to be paid in order to read the value of the variable. Given a function f and an assignment σ to the variables of f, the performance of an algorithm for evaluating f is measured via the competitive ratio, i.e., the ratio of the total cost spent by the algorithm and the cost of the cheapest set of variables constituting a certificate for the value of the function on the given assignment.