{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T11:22:02Z","timestamp":1774956122969,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662489703","type":"print"},{"value":"9783662489710","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48971-0_20","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T04:00:57Z","timestamp":1448510457000},"page":"223-234","source":"Crossref","is-referenced-by-count":3,"title":["Trading off Worst and Expected Cost in Decision Tree Problems"],"prefix":"10.1007","author":[{"given":"Aline","family":"Saettler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo","family":"Laber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferdinando","family":"Cicalese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"M Adler","year":"2008","unstructured":"Adler, M., Heeringa, B.: Approximating optimal binary decision trees. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 1\u20139. Springer, Heidelberg (2008)"},{"key":"20_CR2","unstructured":"Aslam, J.A., Rasala, A., Stein, C., Young, N.E.: Improved bicriteria existence theorems for scheduling. In: SODA, pp. 846\u2013847 (1999)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-16248-0_51","volume-title":"Rough Set and Knowledge Technology","author":"A Alkhalid","year":"2010","unstructured":"Alkhalid, A., Chikalov, I., Moshkov, M.: A tool for study of optimal decision trees. In: Yu, J., Greco, S., Lingras, P., Wang, G., Skowron, A. (eds.) RSKT 2010. LNCS, vol. 6401, pp. 353\u2013360. Springer, Heidelberg (2010)"},{"key":"20_CR4","volume-title":"Nonlinear Programming: Theory and Algorithms","author":"MS Bazaraa","year":"1993","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 2nd edn. John Wiley, New York (1993)","edition":"2"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","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-IT 58(1), 459\u2013478 (2012)","journal-title":"IEEE-IT"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(93)90207-P","volume":"45","author":"M Buro","year":"1993","unstructured":"Buro, M.: On the maximum length of huffman codes. IPL 45, 219\u2013223 (1993)","journal-title":"IPL"},{"key":"20_CR7","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 2007, pp. 53\u201362 (2007)","DOI":"10.1145\/1265530.1265538"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-17514-5_18","volume-title":"Algorithms and Computation","author":"F Cicalese","year":"2010","unstructured":"Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: On greedy algorithms for decision trees. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol. 6507, pp. 206\u2013217. Springer, Heidelberg (2010)"},{"key":"20_CR9","unstructured":"Cicalese, F., Laber, E., Saettler, A.: Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In: ICML 2014, pp. 414\u2013422 (2014)"},{"issue":"2","key":"20_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1137\/0123019","volume":"23","author":"MR Garey","year":"1972","unstructured":"Garey, M.R.: Optimal binary identification procedures. SIAM J. Appl. Math. 23(2), 173\u2013186 (1972)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/0203008","volume":"3","author":"MR Garey","year":"1974","unstructured":"Garey, M.R.: Optimal binary search trees with restricted maximal depth. SIAM J. Comput. 3(2), 101\u2013110 (1974)","journal-title":"SIAM J. Comput."},{"key":"20_CR12","unstructured":"Golovin, D., Krause, A., Ray, D.: Near-optimal bayesian active learning with noisy observations. In: Advances in Neural Information Processing Systems, vol. 23, pp. 766\u2013774 (2010)"},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-642-04414-4_15","volume-title":"Algorithmic Learning Theory","author":"A Guillory","year":"2009","unstructured":"Guillory, A., Bilmes, J.: Average-case active learning with costs. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS, vol. 5809, pp. 141\u2013155. Springer, Heidelberg (2009)"},{"key":"20_CR14","unstructured":"Guillory, A., Bilmes, J.: Interactive submodular set cover. In: Proceedings of ICML 2010, pp. 415\u2013422 (2010)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-14165-2_58","volume-title":"Automata, Languages and Programming","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Approximation algorithms for optimal decision trees and adaptive TSP problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 690\u2013701. Springer, Heidelberg (2010)"},{"key":"20_CR16","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-319-01866-9_13","volume-title":"Innovations in Intelligent Machines-4","author":"S Hussain","year":"2014","unstructured":"Hussain, S.: Relationships among various parameters for decision tree optimization. In: Faucher, C., Jain, L.C. (eds.) Innovations in Intelligent Machines-4. SCI, vol. 514, pp. 393\u2013410. Springer, Heidelberg (2014)"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.ijpe.2014.06.009","volume":"157","author":"P Kelle","year":"2014","unstructured":"Kelle, P., Schneider, H., Yi, H.: Decision alternatives between expected cost minimization and worst case scenario in emergency supply second revision. Int. J. Prod. Econ. 157, 250\u2013260 (2014)","journal-title":"Int. J. Prod. Econ."},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Algorithms and Data Structures","author":"SR Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Przytycka, T.M., Borgstrom, R.: On an optimal split tree problem. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 157\u2013168. Springer, Heidelberg (1999)"},{"key":"20_CR19","unstructured":"Krause, A.: Optimizing Sensing: Theory and Applications. Ph.D. thesis, Carnegie Mellon University, December 2008"},{"issue":"6","key":"20_CR20","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1137\/0216070","volume":"16","author":"LL Larmore","year":"1987","unstructured":"Larmore, L.L.: Height restricted optimal binary trees. SICOMP 16(6), 1115\u20131123 (1987)","journal-title":"SICOMP"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","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. J. ACM 37(3), 464\u2013473 (1990)","journal-title":"J. ACM"},{"issue":"4","key":"20_CR22","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s00453-001-0060-4","volume":"31","author":"RL Milidi","year":"2001","unstructured":"Milidi, R.L., Laber, E.S.: Bounding the inefficiency of length-restricted prefix codes. Algorithmica 31(4), 513\u2013529 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"20_CR23","doi-asserted-by":"crossref","first-page":"285","DOI":"10.3233\/FI-2010-350","volume":"104","author":"MJ Moshkov","year":"2010","unstructured":"Moshkov, M.J.: Greedy algorithm with weights for decision tree construction. Fundam. Inform. 104(3), 285\u2013292 (2010)","journal-title":"Fundam. Inform."},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: FOCS 2000, pp. 86\u201392 (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"key":"20_CR25","unstructured":"Rasala, A., Stein, C., Torng, E., Uthaisombut, P.: Existence theorems, lower bounds and algorithms for scheduling to meet two objectives. In: SODA 2002, pp. 723\u2013731 (2002)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T15:12:05Z","timestamp":1748704325000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}