×

Evaluation of monotone DNF formulas. (English) Zbl 1364.68221

Summary: Stochastic Boolean function evaluation (SBFE) is the problem of determining the value of a given Boolean function \(f\) on an unknown input \(x\), when each bit \(x_i\) of \(x\) can only be determined by paying a given associated cost \(c_i\). Further, \(x\) is drawn from a given product distribution: for each \(x_i\), \(\mathbf{Pr}[x_i=1] = p_i\) and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bar-Noy, A., Bellare, M., Halldórsson, M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inform. Comput. 140(2), 183-202 (1998) · Zbl 0895.68022 · doi:10.1006/inco.1997.2677
[2] Bellala, G., Bhavnani, S.K., Scott, C.: Group-based active query selection for rapid diagnosis in time-critical situations. Inst. Elect. Electron. Eng. Trans. Inform. Theory 58(1), 459-478 (2012) · Zbl 1365.62303
[3] Boros, E., Ünlüyurt, T.: Computing tools for modeling, optimization and simulation, operations research/computer science interfaces series. In: Sequential Testing of Series-Parallel Systems of Small Depth, vol. 12, pp. 39-73. Springer, Heidelberg (2000)
[4] Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci. 64(4), 785-819 (2002) · Zbl 1015.68244 · doi:10.1006/jcss.2002.1828
[5] Chvátal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233-235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[6] Cicalese, F., Gagie, T., Laber, E., Milanič, M.: Competitive boolean function evaluation: beyond monotonicity, and the symmetric case. Discret. Appl. Math. 159(11), 1070-1078 (2011) · Zbl 1247.06011 · doi:10.1016/j.dam.2010.05.016
[7] Cicalese, F., Laber, E.: On the competitive ratio of evaluating priced functions. J. ACM 58(3), 9:1-9:40 (2011) · Zbl 1327.68128
[8] Cicalese, F., Laber, E., Saettler, A.M.: Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In: Proceedings of the 31st International Conference on Machine Learning, pp. 414-422 (2014)
[9] Cox, L.A., Qiu, Y., Kuehner, W.: Heuristic least-cost computation of discrete classification functions with uncertain argument values. Ann. Oper. Res. 21(1-4), 1-29 (1989). Linkages with artificial intelligence · Zbl 0705.90089
[10] Deshpande, A., Hellerstein, L.: Flow algorithms for parallel query optimization. In: IEEE 24th International Conference on Data Endineering, pp. 754-763. IEEE (2008) · Zbl 1131.68524
[11] Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic boolean function evaluation and stochastic submodular set cover (2013). arXiv:1303.0726 · Zbl 1421.68212
[12] Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1453-1467 (2014) · Zbl 1421.68212
[13] Feige, U.: A threshold of \[\ln n\] lnn for approximating set cover. J. ACM 45, 314-318 (1998) · Zbl 0922.68067 · doi:10.1145/285055.285059
[14] Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427-486 (2011) · Zbl 1230.90141
[15] Golovin, D., Krause, A., Ray, D.: Near-optimal Bayesian active learning with noisy observations. In: Conference proceeding in the 23rd annual NIPS. Advances in Neural Information Processing Systems, pp. 766-774 (2010) · Zbl 0922.68067
[16] Greiner, R., Hayward, R., Jankowska, M., Molloy, M.: Finding optimal satisficing strategies for AND-OR trees. Artif. Intell. 170(1), 19-58 (2006) · Zbl 1131.68524 · doi:10.1016/j.artint.2005.09.002
[17] Guijarro, D., Lavín, V., Raghavan, V.: Exact learning when irrelevant variables abound. Inform. Process. Lett. 70(5), 233-239 (1999) · Zbl 1002.68074 · doi:10.1016/S0020-0190(99)00063-0
[18] Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555-556 (1982) · Zbl 0486.68067 · doi:10.1137/0211045
[19] Ibaraki, T., Kameda, T.: On the optimal nesting order for computing \[NN\]-relational joins. ACM Trans. Database Syst. 9(3), 482-502 (1984) · doi:10.1145/1270.1498
[20] Kaplan, H., Kushilevitz, E., Mansour, Y.: Learning with attribute costs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 356-365 (2005) · Zbl 1192.68392
[21] Krishnamurthy, R., Boral, H., Zaniolo, C.: Optimization of nonrecursive queries. In: Proceedings of the 12th International Conference on Very Large Data Bases, vol. 86, pp. 128-137 (1986) · Zbl 1015.68244
[22] Moshkov, M., Chikalov, I.: Bounds on average weighted depth of decision trees. Fundam. Inform. 31(2), 145-156 (1997) · Zbl 0888.68054
[23] Moshkov, M.J.: Approximate algorithm for minimization of decision tree depth. In: Wang, G., Liu, Q., Yao, Y., Skowron, A., (eds.) Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 611-614. Springer, Heidelberg (2003) · Zbl 1026.68604
[24] Munagala, K., Babu, S., Motwani, R., Widom, J.: The pipelined set cover problem. In: Proceedings of the 10th International Conference on Database Theory, pp. 83-98. Springer (2005) · Zbl 1112.68373
[25] Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433-436 (2011) · Zbl 1235.90131 · doi:10.1016/j.orl.2011.08.002
[26] Srivastava, U., Munagala, K., Widom, J., Motwani, R.: Query optimization over web services. In: Proceedings of the 32nd international conference on Very Large Data Bases, pp. 355-366. VLDB Endowment (2006) · Zbl 1002.68074
[27] Ünlüyurt, T.: Sequential testing of complex systems: a review. Discret. Appl. Math. 142(1-3), 189-205 (2004) · Zbl 1077.68541 · doi:10.1016/j.dam.2002.08.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.