The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions
The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions
复制标题
对称布尔函数的随机布尔函数求值问题
DOI：
10.1016/j.dam.2021.12.001
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Kletenik, Devorah
中科院分区：
文献类型：
--
作者：
Gkenosis, Dimitrios;Grammel, Nathaniel;Hellerstein, Lisa;Kletenik, Devorah
本文给出了两个求解对称布尔函数随机赋值问题的近似算法。首先是一个O（log n）-近似算法，基于子模块的目标值方法的Deshpande，Hellerstein和Kletenik。我们的第二个算法，这是简单的，是基于算法解决SBFE问题的k-of-n函数，由于Salloum，布鲁尔，和Ben-Dov。它实现了（B− 1）近似因子，其中B是对称布尔函数的标准向量表示中0和1的块的数量。作为第一个算法设计的一部分，我们证明了任何对称布尔函数的目标值小于n（n+ 1）/2。最后，我们给出了一个例子表明，对于对称布尔函数，最小期望验证成本和最小期望评估成本不一定相等。这与Das、Jafarpour、Orlitsky、Pan和Suresh给出的先前结果形成对比，该结果表明单位成本情况下等式成立。
We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O (log n)-approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k-of-n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B− 1) approximation factor, where B is the number of blocks of 0’s and 1’s in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n (n+ 1)/2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case.