The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
| Autor: | Gkenosis, Dimitrios, Grammel, Nathaniel, Hellerstein, Lisa, Kletenik, Devorah |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Discrete Applied Mathematics 309 (2022), 269-277 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.dam.2021.12.001 |
| Popis: | 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. Comment: Preliminary versions of these results appeared on Arxiv in arXiv:1806.10660. That paper contains results for both arbitrary costs and unit costs. This paper considers only arbitrary costs. Updated January 2022 include journal information |
| Databáze: | arXiv |
| Externí odkaz: |
|