Approximating decision trees with value dependent testing costs

We study the problem of evaluating a discrete function by adaptively querying the values of its variables. Reading the value of a variable is done at the expense of some cost, and the goal is to design a strategy (decision tree) with low cost for evaluating the function. In this paper, we study a variant of this problem in which the cost of reading a variable depends on the variable's value. We provide an O(log⁡n) approximation algorithm for the minimization of the worst cost when every variable assumes at most two values, which is the best possible approximation under the assumption P≠NP. For the general case where the variables may assume more than 2 values we present an n-approximation.