{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:28:45Z","timestamp":1767140925259,"version":"build-2238731810"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T00:00:00Z","timestamp":1473897600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0211-2","type":"journal-article","created":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T09:40:33Z","timestamp":1473932433000},"page":"886-908","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Trading Off Worst and Expected Cost in Decision Tree Problems"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9498-7835","authenticated-orcid":false,"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":[[2016,9,15]]},"reference":[{"issue":"3","key":"211_CR1","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1007\/s00453-011-9510-9","volume":"62","author":"M Adler","year":"2012","unstructured":"Adler, M., Heeringa, B.: Approximating optimal binary decision trees. Algorithmica 62(3), 1112\u20131121 (2012)","journal-title":"Algorithmica"},{"key":"211_CR2","unstructured":"Aslam, J.A., Rasala, A., Stein, C., Young, N.E.: Improved bicriteria existence theorems for scheduling. In: SODA 1999, pp. 846\u2013847 (1999)"},{"key":"211_CR3","first-page":"353","volume":"6401","author":"A Alkhalid","year":"2010","unstructured":"Alkhalid, A., Chikalov, I., Moshkov, M.: A tool for study of optimal decision trees. LNCS 6401, 353\u2013360 (2010)","journal-title":"LNCS"},{"key":"211_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. Wiley, New York (1993)","edition":"2"},{"issue":"1","key":"211_CR5","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-IT 58(1), 459\u2013478 (2012)","journal-title":"IEEE-IT"},{"issue":"5","key":"211_CR6","doi-asserted-by":"crossref","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(5), 219\u2013223 (1993)","journal-title":"IPL"},{"issue":"2","key":"211_CR7","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/1921659.1921661","volume":"7","author":"VT Chakaravarthy","year":"2011","unstructured":"Chakaravarthy, V.T., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision trees for entity identification: approximation algorithms and hardness results. ACM Trans. Algorithms 7(2), 15:1\u201315:22 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"211_CR8","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: On greedy algorithms for decision trees. In: Proceedings of ISAAC (2010)","DOI":"10.1007\/978-3-642-17514-5_18"},{"key":"211_CR9","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":"2","key":"211_CR10","doi-asserted-by":"crossref","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":"211_CR11","doi-asserted-by":"crossref","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":"211_CR12","first-page":"766","volume":"23","author":"D Golovin","year":"2010","unstructured":"Golovin, D., Krause, A., Ray, D.: Near-optimal bayesian active learning with noisy observations. Adv. Neural Inf. Proc. Syst. 23, 766\u2013774 (2010)","journal-title":"Adv. Neural Inf. Proc. Syst."},{"key":"211_CR13","doi-asserted-by":"crossref","unstructured":"Guillory, A., Bilmes, J.: Average-case active learning with costs. In: ALT\u201909, pp. 141\u2013155 (2009)","DOI":"10.1007\/978-3-642-04414-4_15"},{"key":"211_CR14","unstructured":"Guillory, A., Bilmes, J.: Interactive submodular set cover. In: Proceedings of ICML10, pp. 415\u2013422 (2010)"},{"key":"211_CR15","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":"211_CR16","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-319-01866-9_13","volume":"514","author":"S Hussain","year":"2014","unstructured":"Hussain, S.: Relationships among various parameters for decision tree optimization. Stud. Comput. Intell. 514, 393\u2013410 (2014)","journal-title":"Stud. Comput. Intell."},{"key":"211_CR17","doi-asserted-by":"crossref","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":"211_CR18","first-page":"157","volume":"99","author":"S Kosaraju","year":"1999","unstructured":"Kosaraju, S., Przytycka, T., Borgstrom, R.: On an optimal split tree problem. WADS 99, 157\u2013168 (1999)","journal-title":"WADS"},{"key":"211_CR19","unstructured":"Krause, A.: Optimizing sensing: theory and applications. Ph.D. thesis, Carnegie Mellon University (2008)"},{"issue":"6","key":"211_CR20","doi-asserted-by":"crossref","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":"211_CR21","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. J. ACM 37(3), 464\u2013473 (1990)","journal-title":"J. ACM"},{"issue":"4","key":"211_CR22","doi-asserted-by":"crossref","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":"211_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. Fundamentae Informaticae 104(3), 285\u2013292 (2010)","journal-title":"Fundamentae Informaticae"},{"key":"211_CR24","first-page":"86","volume":"2000","author":"CH Papadimitriou","year":"2000","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. FOCS 2000, 86\u201392 (2000)","journal-title":"FOCS"},{"key":"211_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)"},{"key":"211_CR26","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)"}],"updated-by":[{"DOI":"10.1007\/s00453-018-0423-8","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0211-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0211-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0211-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T11:21:20Z","timestamp":1657279280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0211-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,15]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["211"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0211-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,15]]}}}