On the competitive ratio of evaluating priced functions

Let f be a function on a set of variables V. For each x ∈ V, let c(x) be the cost of reading the value of x. An algorithm for evaluating f is a strategy for adaptively identifying and reading a set of variables U ⊆ V whose values uniquely determine the value of f. We are interested in finding algorithms which minimize the cost incurred to evaluate f in the above sense. Competitive analysis is employed to measure the performance of the algorithms. We address two variants of the above problem. We consider the basic model in which the evaluation algorithm knows the cost c(x), for each x ∈ V. We also study a novel model where the costs of the variables are not known in advance and some preemption is allowed in the reading operations. This model has applications, for example, when reading a variable coincides with obtaining the output of a job on a CPU and the cost is the CPU time.

For the model where the costs of the variables are known, we present a polynomial time algorithm with the best possible competitive ratio γ_c^f for each function f that is representable by a threshold tree and for each fixed cost function c(⋅). Remarkably, the best-known result for the same class of functions is a pseudo-polynomial algorithm with competitiveness 2 γ_c^f. Still in the same model, we introduce the Linear Programming Approach (LPA), a framework that allows the design of efficient algorithms for evaluating functions. We show that different implementations of this approach lead in general to the best algorithms known so far—and in many cases to optimal algorithms—for different classes of functions considered before in the literature.

Via the LPA, we are able to determine exactly the optimal extremal competitiveness of monotone Boolean functions. Remarkably, the upper bound which leads to this result, holds for a much broader class of functions, which also includes the whole set of Boolean functions.

We also show how to extend the LPA (together with these results) to the model where the costs of the variables are not known beforehand. In particular, we show how to employ the extended LPA to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees.