Competitive evaluation of threshold functions in the priced information model

Competitive evaluation of threshold functions in the priced information model

0.00 Avg rating0 Votes
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: ,
Abstract:

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 f and an assignment σ to the variables of f, the performance of an algorithm for evaluating f is measured via the competitive ratio, i.e., the ratio of the total cost spent by the algorithm and the cost of the cheapest set of variables constituting a certificate for the value of the function on the given assignment. In Cicalese and Laber (2008) a new LP based approach (the ℒ𝒫𝒜 equ1 ) was introduced for designing competitive algorithms in the framework described by Charikar et al. The ℒ𝒫𝒜 equ2 is based on the solution of a linear program defined on the set of certificates of the function in question. Cicalese and Laber proved that for any monotone Boolean function the ℒ𝒫𝒜 equ3 provides algorithms with the best extremal competitive ratio (i.e., w.r.t. the worst case costs). The existence of an efficient implementation of the ℒ𝒫𝒜 equ4 for general monotone Boolean functions remains a major open problem. We focus on the class of threshold functions, which generalize k‐out‐of‐n functions and have applications in several contexts. We show an interesting connection between the separating structures of threshold functions and the solution of the LP used by the ℒ𝒫𝒜 . equ5 A direct consequence of this result is the existence of a polynomial implementation of the ℒ𝒫𝒜 equ6 with the best competitiveness against the worst case costs for threshold functions given via a separating structure. We also show that a pseudo‐polynomial implementation of the ℒ𝒫𝒜 equ7 exists for the class of functions that are representable by read once formulas whose connectives are threshold functions given by their separating structure. In the case the threshold functions are provided via their complete DNF our algorithm runs in polynomial time.

Reviews

Required fields are marked *. Your email address will not be published.