Thumbnail
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

   Open content in new tab
Source: ACM Digital Library