In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 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 (Proceedings of the 35th international colloquium on automata languages and programming, pp. 173–185, Springer, Berlin, 2008) a new LP based approach (the LPA) was introduced for designing competitive algorithms in the framework described by Charikar et al. The LPA 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 LPA 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 LPA 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 LPA. A direct consequence of this result is the existence of a polynomial implementation of the LPA 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 LPA 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.
Competitive Evaluation of Threshold Functions in the Priced Information Model
CICALESE, Ferdinando;
2011-01-01
Abstract
In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 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 (Proceedings of the 35th international colloquium on automata languages and programming, pp. 173–185, Springer, Berlin, 2008) a new LP based approach (the LPA) was introduced for designing competitive algorithms in the framework described by Charikar et al. The LPA 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 LPA 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 LPA 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 LPA. A direct consequence of this result is the existence of a polynomial implementation of the LPA 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 LPA 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
