{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:39:55Z","timestamp":1768711195632,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T00:00:00Z","timestamp":1477008000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["305945\/2013-0"],"award-info":[{"award-number":["305945\/2013-0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CNPQ","award":["477946\/2013-5"],"award-info":[{"award-number":["477946\/2013-5"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0225-9","type":"journal-article","created":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T17:43:49Z","timestamp":1477071829000},"page":"763-796","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Decision Trees for Function Evaluation: Simultaneous Optimization of Worst and Expected Cost"],"prefix":"10.1007","volume":"79","author":[{"given":"Ferdinando","family":"Cicalese","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo","family":"Laber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aline","family":"Saettler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,21]]},"reference":[{"key":"225_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Heeringa, B.: Approximating optimal binary decision trees. APPROX\/RANDOM \u201908, pp. 1\u20139 (2008)","DOI":"10.1007\/978-3-540-85363-3_1"},{"key":"225_CR2","doi-asserted-by":"crossref","unstructured":"Allen, S.R., Hellerstein, L., Kletenik, D., \u00dcnl\u00fcyurt, T.: Evaluation of DNF Formulas. In: Proceedings of ISAIM (2014)","DOI":"10.1007\/s00453-015-0092-9"},{"key":"225_CR3","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Meijer, H., Mitchell, J.S.B., Rappaport, D., Skiena, S.S.: Decision trees for geometric models. In: Proceedings of SCG \u201993, pp. 369\u2013378 (1993)","DOI":"10.1145\/160985.161167"},{"issue":"1","key":"225_CR4","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/TIT.2011.2169296","volume":"58","author":"G Bellala","year":"2012","unstructured":"Bellala, G., Bhavnani, S.K., Scott, C.: Group-based active query selection for rapid diagnosis in time-critical situations. IEEE Trans. Inf. Theor. 58(1), 459\u2013478 (2012)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"225_CR5","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V.T., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision trees for entity identification: approximation algorithms and hardness results. In: Proceedings of PODS \u201907, pp. 53\u201362 (2007)","DOI":"10.1145\/1265530.1265538"},{"key":"225_CR6","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V.T., Pandit, V., Roy, S., Sabharwal, Y.: Approximating decision trees with multiway branches. In: Proceedings of ICALP \u201909, pp. 210\u2013221 (2009)","DOI":"10.1007\/978-3-642-02927-1_19"},{"issue":"4","key":"225_CR7","doi-asserted-by":"crossref","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.M., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci. 64(4), 785\u2013819 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"225_CR8","unstructured":"Cicalese, F., Laber, E., Saettler, A. Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In: ICML2014, pp. 414\u2013422 (2014)"},{"issue":"3","key":"225_CR9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/1970392.1970393","volume":"58","author":"F Cicalese","year":"2011","unstructured":"Cicalese, F., Laber, E.S.: On the competitive ratio of evaluating priced functions. J. ACM 58(3), 9 (2011)","journal-title":"J. ACM"},{"key":"225_CR10","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: On greedy algorithms for decision trees. In: Proceedings of ISAAC\u201910 (2010)","DOI":"10.1007\/978-3-642-17514-5_18"},{"key":"225_CR11","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"225_CR12","unstructured":"Dasgupta, S.: Analysis of a greedy active learning strategy. In: NIPS\u201904 (2004)"},{"key":"225_CR13","first-page":"1453","volume":"2014","author":"A Deshpande","year":"2014","unstructured":"Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover. Proc. SODA 2014, 1453\u20131467 (2014)","journal-title":"Proc. SODA"},{"key":"225_CR14","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ ln n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"225_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1137\/0123019","volume":"23","author":"M Garey","year":"1972","unstructured":"Garey, M.: Optimal binary identification procedures. SIAM J. Appl. Math. 23(2), 173\u2013186 (1972)","journal-title":"SIAM J. Appl. Math."},{"key":"225_CR16","unstructured":"Golovin, D., Krause, A., Ray, D.: Near-optimal bayesian active learning with noisy observations. In: Proceedings of NIPS\u201910, pp. 766\u2013774 (2010)"},{"key":"225_CR17","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."},{"issue":"1","key":"225_CR18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.artint.2005.09.002","volume":"170","author":"R Greiner","year":"2005","unstructured":"Greiner, R., Howard, R., Jankowska, M., Malloy, M.: Finding optimal satisfiscing strategies for and-or trees. Artif. Intell. 170(1), 19\u201358 (2005)","journal-title":"Artif. Intell."},{"key":"225_CR19","doi-asserted-by":"crossref","unstructured":"Guillory, A., Bilmes, J.: Average-case active learning with costs. In: Proceedings of ALT\u201909, pp. 141\u2013155 (2009)","DOI":"10.1007\/978-3-642-04414-4_15"},{"key":"225_CR20","unstructured":"Guillory, A., Bilmes, J.: Interactive submodular set cover. In: Proceedings of ICML\u201910, pp. 415\u2013422 (2010)"},{"key":"225_CR21","unstructured":"Guillory, A., Bilmes, J.: Simultaneous learning and covering with adversarial noise. In: ICML\u201911, pp. 369\u2013376 (2011)"},{"key":"225_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Approximation algorithms for optimal decision trees and adaptive tsp problems. In: Proceedings of ICALP\u201910, pp. 690\u2013701 (2010)","DOI":"10.1007\/978-3-642-14165-2_58"},{"key":"225_CR23","unstructured":"Hanneke, S.: The cost complexity of interactive learning. unpublished (2006)"},{"issue":"1","key":"225_CR24","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L Hyafil","year":"1976","unstructured":"Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is np-complete. Inf. Process. Lett. 5(1), 15\u201317 (1976)","journal-title":"Inf. Process. Lett."},{"key":"225_CR25","first-page":"356","volume":"2005","author":"H Kaplan","year":"2005","unstructured":"Kaplan, H., Kushilevitz, E., Mansour, Y.: Learning with attribute costs. Proc. STOC 2005, 356\u2013365 (2005)","journal-title":"Proc. STOC"},{"key":"225_CR26","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R., Przytycka, T.M., Borgstrom, R.S.: On an optimal split tree problem. In: Proceedings of WADS \u201999, pp. 157\u2013168 (1999)","DOI":"10.1007\/3-540-48447-7_17"},{"key":"225_CR27","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.dam.2004.06.002","volume":"144","author":"ES Laber","year":"2004","unstructured":"Laber, E.S., Nogueira, L.T.: On the hardness of the minimum height decision tree problem. Discrete Appl. Math. 144, 209\u2013212 (2004)","journal-title":"Discrete Appl. Math."},{"key":"225_CR28","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1145\/79147.79150","volume":"37","author":"LL Larmore","year":"1990","unstructured":"Larmore, L.L., Hirschberg, D.S.: A fast algorithm for optimal length-limited huffman codes. JACM 37, 464\u2013473 (1990)","journal-title":"JACM"},{"key":"225_CR29","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1145\/356893.356898","volume":"14","author":"BME Moret","year":"1982","unstructured":"Moret, B.M.E.: Decision trees and diagrams. ACM Comput. Surv. 14, 593\u2013623 (1982)","journal-title":"ACM Comput. Surv."},{"key":"225_CR30","doi-asserted-by":"crossref","unstructured":"Moshkov, J.M.: Approximate algorithm for minimization of decision tree depth. In: Proceedings of 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 611\u2013614 (2003)","DOI":"10.1007\/3-540-39205-X_100"},{"key":"225_CR31","doi-asserted-by":"crossref","first-page":"285","DOI":"10.3233\/FI-2010-350","volume":"104","author":"JM Moshkov","year":"2010","unstructured":"Moshkov, J.M.: Greedy algorithm with weights for decision tree construction. Fundam. Inf. 104, 285\u2013292 (2010)","journal-title":"Fundam. Inf."},{"key":"225_CR32","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"225_CR33","doi-asserted-by":"crossref","unstructured":"Nevmyvaka, Y., Feng, Y., Kearns, M.: Reinforcement learning for optimized trade execution. In: Proceedings of ICML\u201906, pp. 673\u2013680 (2006)","DOI":"10.1145\/1143844.1143929"},{"key":"225_CR34","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"225_CR35","doi-asserted-by":"crossref","unstructured":"Saettler A., Laber, E., Cicalese, F.: Trading off worst and expected cost in decision tree problems. In: Proceedings of ISAAC 2015 (2015, to appear)","DOI":"10.1007\/978-3-662-48971-0_20"},{"key":"225_CR36","doi-asserted-by":"crossref","unstructured":"Saks, M.E., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proceedings of FOCS\u201986, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"issue":"1","key":"225_CR37","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"225_CR38","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/2402.322383","volume":"30","author":"M Tarsi","year":"1983","unstructured":"Tarsi, M.: Optimal search on some game trees. J. ACM 30(3), 389\u2013396 (1983)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"225_CR39","doi-asserted-by":"crossref","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. Discrete Appl. Math. 142(1\u20133), 189\u2013205 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"225_CR40","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L Wolsey","year":"1982","unstructured":"Wolsey, L.: Maximising real-valued submodular functions. Math. Oper. Res. 7(3), 410\u2013425 (1982)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0225-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0225-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0225-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T21:17:58Z","timestamp":1601155078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0225-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,21]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["225"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0225-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,21]]}}}