{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T14:10:08Z","timestamp":1773583808831,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T00:00:00Z","timestamp":1447891200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T00:00:00Z","timestamp":1447891200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0917153"],"award-info":[{"award-number":["0917153"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0946825"],"award-info":[{"award-number":["0946825"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1116594"],"award-info":[{"award-number":["CCF-1116594"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1217968"],"award-info":[{"award-number":["1217968"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0917153"],"award-info":[{"award-number":["0917153"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"TUBITAK","award":["2219 programme"],"award-info":[{"award-number":["2219 programme"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0747250"],"award-info":[{"award-number":["CCF-0747250"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["Graduate Research Fellowship Program under Grant No. DGE-1252522."],"award-info":[{"award-number":["Graduate Research Fellowship Program under Grant No. DGE-1252522."]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0092-9","type":"journal-article","created":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T14:42:25Z","timestamp":1447944145000},"page":"661-685","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Evaluation of Monotone DNF Formulas"],"prefix":"10.1007","volume":"77","author":[{"given":"Sarah R.","family":"Allen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lisa","family":"Hellerstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devorah","family":"Kletenik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tongu\u00e7","family":"\u00dcnl\u00fcyurt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,19]]},"reference":[{"issue":"2","key":"92_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Bellare, M., Halld\u00f3rsson, M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inform. Comput. 140(2), 183\u2013202 (1998)","journal-title":"Inform. Comput."},{"key":"92_CR2","unstructured":"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\u2013478 (2012)"},{"key":"92_CR3","doi-asserted-by":"crossref","unstructured":"Boros, E., \u00dcnl\u00fcyurt, 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\u201373. Springer, Heidelberg (2000)","DOI":"10.1007\/978-1-4615-4567-5_3"},{"issue":"4","key":"92_CR4","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1006\/jcss.2002.1828","volume":"64","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci. 64(4), 785\u2013819 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"92_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"11","key":"92_CR6","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.dam.2010.05.016","volume":"159","author":"F Cicalese","year":"2011","unstructured":"Cicalese, F., Gagie, T., Laber, E., Milani\u010d, M.: Competitive boolean function evaluation: beyond monotonicity, and the symmetric case. Discret. Appl. Math. 159(11), 1070\u20131078 (2011)","journal-title":"Discret. Appl. Math."},{"key":"92_CR7","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Laber, E.: On the competitive ratio of evaluating priced functions. J. ACM 58(3), 9:1\u20139:40 (2011)","DOI":"10.1145\/1970392.1970393"},{"key":"92_CR8","unstructured":"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\u2013422 (2014)"},{"key":"92_CR9","doi-asserted-by":"crossref","unstructured":"Cox, L.A., Qiu, Y., Kuehner, W.: Heuristic least-cost computation of discrete classification functions with uncertain argument values. Ann. Oper. Res. 21(1\u20134), 1\u201329 (1989). Linkages with artificial intelligence","DOI":"10.1007\/BF02022091"},{"key":"92_CR10","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Hellerstein, L.: Flow algorithms for parallel query optimization. In: IEEE 24th International Conference on Data Endineering, pp. 754\u2013763. IEEE (2008)","DOI":"10.1109\/ICDE.2008.4497484"},{"key":"92_CR11","unstructured":"Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic boolean function evaluation and stochastic submodular set cover (2013). \n                    arXiv:1303.0726"},{"key":"92_CR12","doi-asserted-by":"crossref","unstructured":"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\u20131467 (2014)","DOI":"10.1137\/1.9781611973402.107"},{"key":"92_CR13","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45, 314\u2013318 (1998)","journal-title":"J. ACM"},{"key":"92_CR14","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427\u2013486 (2011)","journal-title":"J. Artif. Intell. Res."},{"key":"92_CR15","unstructured":"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\u2013774 (2010)"},{"issue":"1","key":"92_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.artint.2005.09.002","volume":"170","author":"R Greiner","year":"2006","unstructured":"Greiner, R., Hayward, R., Jankowska, M., Molloy, M.: Finding optimal satisficing strategies for AND-OR trees. Artif. Intell. 170(1), 19\u201358 (2006)","journal-title":"Artif. Intell."},{"issue":"5","key":"92_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0020-0190(99)00063-0","volume":"70","author":"D Guijarro","year":"1999","unstructured":"Guijarro, D., Lav\u00edn, V., Raghavan, V.: Exact learning when irrelevant variables abound. Inform. Process. Lett. 70(5), 233\u2013239 (1999)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"92_CR18","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"92_CR19","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1145\/1270.1498","volume":"9","author":"T Ibaraki","year":"1984","unstructured":"Ibaraki, T., Kameda, T.: On the optimal nesting order for computing $$N$$-relational joins. ACM Trans. Database Syst. 9(3), 482\u2013502 (1984)","journal-title":"ACM Trans. Database Syst."},{"key":"92_CR20","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Kushilevitz, E., Mansour, Y.: Learning with attribute costs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 356\u2013365 (2005)","DOI":"10.1145\/1060590.1060644"},{"key":"92_CR21","unstructured":"Krishnamurthy, R., Boral, H., Zaniolo, C.: Optimization of nonrecursive queries. In: Proceedings of the 12th International Conference on Very Large Data Bases, vol.\u00a086, pp. 128\u2013137 (1986)"},{"issue":"2","key":"92_CR22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.3233\/FI-1997-31204","volume":"31","author":"M Moshkov","year":"1997","unstructured":"Moshkov, M., Chikalov, I.: Bounds on average weighted depth of decision trees. Fundam. Inform. 31(2), 145\u2013156 (1997)","journal-title":"Fundam. Inform."},{"key":"92_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013614. Springer, Heidelberg (2003)","DOI":"10.1007\/3-540-39205-X_100"},{"key":"92_CR24","doi-asserted-by":"crossref","unstructured":"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\u201398. Springer (2005)","DOI":"10.1007\/978-3-540-30570-5_6"},{"issue":"6","key":"92_CR25","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.orl.2011.08.002","volume":"39","author":"M Skutella","year":"2011","unstructured":"Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433\u2013436 (2011)","journal-title":"Oper. Res. Lett."},{"key":"92_CR26","unstructured":"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\u2013366. VLDB Endowment (2006)"},{"issue":"1\u20133","key":"92_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.dam.2002.08.001","volume":"142","author":"T \u00dcnl\u00fcyurt","year":"2004","unstructured":"\u00dcnl\u00fcyurt, T.: Sequential testing of complex systems: a review. Discret. Appl. Math. 142(1\u20133), 189\u2013205 (2004)","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0092-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0092-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0092-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0092-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:32:04Z","timestamp":1589697124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0092-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,19]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["92"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0092-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,19]]},"assertion":[{"value":"19 May 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}