A new strategy for querying priced information
A new strategy for querying priced information
复制标题
查询价格信息的新策略
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
E. Laber
中科院分区：
文献类型：
--
作者：
F. Cicalese;E. Laber
本文聚焦于有价信息计算背景下的竞争函数评估。给定一个函数$f$以及$f$的每个变量$x$的成本$c_x$。读取$x$的值必须支付成本$c_x$。问题是设计算法按顺序查询变量的值以计算函数，同时尽量使产生的总成本最小化。采用竞争分析来评估算法的性能。我们描述了一种在这种设定下设计高效算法的新方法。我们将我们的方法应用于在有价信息计算文献中已被研究的几类函数。在所有考虑的情况中，我们的方法所提供的算法比针对同类函数的已知最佳算法能达到更好的界限。更准确地说，对于单调布尔函数类，我们给出一个具有极值竞争力（$k + l - \sqrt{\min(k, l)}$）的多项式时间算法，其中$k$（$l$）表示在最坏情况下为证明所考虑的函数值为1（0）必须读取的变量的最小数量。这极大地改进了已知的最佳结果，即一个指数时间的$2\max(k, l)$ - 竞争算法。对于被称为阈值树的单调布尔函数子类，我们进一步改进了我们的界限，并给出一个具有极值竞争比为$1.618\max(k, l)$的多项式时间算法。然后我们将我们的方法应用于非布尔函数类。我们考虑所谓的博弈树的情况。我们改进了先前针对此类函数发表的结果，提供了一个具有极值竞争比为$1.5\gamma(f)$的多项式时间算法，其中$\gamma(f)$是任何确定性算法的极值竞争比的下限。最后，我们考虑$f$是$\min$（最小值）函数的情况。在这种情况下，我们能够确定该问题的最优竞争力。实际上我们提供了一个具有（$n - 2$）竞争比的算法，它与已知的下限相匹配。
This paper focuses on competitive function evaluation in the context of computing with priced information. A function f is given together with a cost cx for each variable x of f. The cost cx has to be paid to read the value of x. The problem is to design algorithms that query the values of the variables sequentially in order to compute the function while trying to minimize the total cost incurred. Competitive analysis is employed to evaluate the performance of the algorithms. We describe a novel approach for devising efficient algorithms in this setting. We apply our approach to several classes of functions which have been studied in the literature of computing with priced information. In all cases considered, our approach provides algorithms that achieve better bounds than the best known algorithm for the same class of functions.More precisely, for the class of monotone boolean functions, we give a polynomial time algorithm with extremal competitiveness (k+l - √ min(k,l)) where k (l) denotes the minimum number of variables that one must read, in the worst case, in order to prove that the function under consideration evaluates to 1 (0). This dramatically improves upon the best known result which is an exponential time 2 max(k, l)-competitive algorithm. For the subclass of monotone boolean functions known as Threshold Trees we further improve our bounds and give a polynomial time algorithm with extremal competitive ratio 1.618 max(k, l).We then apply our methodology to classes of non-boolean functions. We consider the case of the so called Game Trees. We improve upon previously published results for this class of functions providing a polynomial time algorithm with extremal competitive ratio 1.5 γ(f), where γ(f) is a lower bound on the extremal competitive ratio of any deterministic algorithm.Finally, we consider the case when f is the function min (minimum). In this case, we are able to determine the optimal competitiveness for the problem. In fact we provide an algorithm with an (n-2)-competitive ratio, which matches the known lower bound.