### On the competitive ratio of evaluating priced functionsOn the competitive ratio of evaluating priced functions Access Restriction
Subscribed

 Author Cicalese, Ferdinando ♦ Laber, Eduardo Sany Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Competitive analysis ♦ Function evaluation ♦ Monotone Boolean functions ♦ Priced information Abstract Let $\textit{f}$ be a function on a set of variables $\textit{V}.$ For each $\textit{x}$ ∈ $\textit{V},$ let $\textit{c(x)}$ be the cost of reading the value of $\textit{x}.$ An algorithm for evaluating $\textit{f}$ is a strategy for adaptively identifying and reading a set of variables $\textit{U}$ ⊆ $\textit{V}$ whose values uniquely determine the value of $\textit{f}.$ We are interested in finding algorithms which minimize the cost incurred to evaluate $\textit{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 $\textit{c(x)},$ for each $\textit{x}$ ∈ $\textit{V}.$ We also study a novel model where the costs of the variables are not known in advance and some $\textit{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 $\textit{f}$ that is representable by a threshold tree and for each fixed cost function $\textit{c}(ṡ).$ Remarkably, the best-known result for the same class of functions is a $\textit{pseudo-polynomial}$ algorithm with competitiveness 2 $γ_{c}^{f}.$ Still in the same model, we introduce the Linear Programming Approach $(\textit{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 $\textit{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 $\textit{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 $\textit{LPA}$ to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2011-06-09 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 58 Issue Number 3 Page Count 40 Starting Page 1 Ending Page 40

#### Open content in new tab

Source: ACM Digital Library