On Priced Function Evaluation

Ferdinando Cicalese

ABSTRACT: A function f of n variables is to be evaluated. Let c_i be the cost of accessing the value of the ith variable. Knowing the values of some of the variables may determine the value of f. We provide algorithms for evaluating if by adaptively accessing values of the variables. The objective is to minimize the sum of the costs of the variables read. We evaluate the competitiveness of the algorithms in two settings: when the algorithm does or does not know the access costs c₁, ... , c_n. We provide polytime algorithms with optimal and quasi-optimal competitiveness for several classes of functions.