Article ID: | iaor20117907 |
Volume: | 188 |
Issue: | 1 |
Start Page Number: | 111 |
End Page Number: | 132 |
Publication Date: | Aug 2011 |
Journal: | Annals of Operations Research |
Authors: | Milanic Martin, Cicalese Ferdinando |
In Charikar et al. (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