{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T09:21:41Z","timestamp":1768728101619,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2011,4,5]],"date-time":"2011-04-05T00:00:00Z","timestamp":1301961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00453-011-9510-9","type":"journal-article","created":{"date-parts":[[2011,4,4]],"date-time":"2011-04-04T12:37:12Z","timestamp":1301920632000},"page":"1112-1121","source":"Crossref","is-referenced-by-count":15,"title":["Approximating Optimal Binary Decision Trees"],"prefix":"10.1007","volume":"62","author":[{"given":"Micah","family":"Adler","sequence":"first","affiliation":[]},{"given":"Brent","family":"Heeringa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,5]]},"reference":[{"key":"9510_CR1","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1109\/FOCS.2004.36","volume-title":"Proceedings of the 45th Annual Symposium on Foundations of Computer Science","author":"M. Alekhnovich","year":"2004","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A.R., Pitassi, T.: Learnability and automatizability. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pp.\u00a0621\u2013630. IEEE Comput. Soc., Los Alamitos (2004)"},{"issue":"3","key":"9510_CR2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0218195998000175","volume":"8","author":"E.M. Arkin","year":"1998","unstructured":"Arkin, E.M., Meijer, H., Mitchell, J.S.B., Rappaport, D., Skiena, S.: Decision trees for geometric models. Int. J. Comput. Geom. Appl. 8(3), 343\u2013364 (1998)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"9510_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2003.06.001","volume":"321","author":"R. Carmo","year":"2004","unstructured":"Carmo, R., Donadelli, J., Kohayakawa, Y., Laber, E.S.: Searching in random partially ordered sets. Theor. Comput. Sci. 321(1), 41\u201357 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9510_CR4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/1265530.1265538","volume-title":"Proceedings of the Twenty-Sixth ACM Symposium on Principles of Database Systems","author":"V.T. Chakaravarthy","year":"2007","unstructured":"Chakaravarthy, V.T., Pandit, V., Roy, S., Awasthi, P., Mohania, M.K.: Decision trees for entity identification: approximation algorithms and hardness results. In: Libkin, L. (ed.) Proceedings of the Twenty-Sixth ACM Symposium on Principles of Database Systems, pp. 53\u201362 (2007)"},{"issue":"4","key":"9510_CR5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U. Feige","year":"2004","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min-sum set cover. Algorithmica 40(4), 219\u2013234 (2004)","journal-title":"Algorithmica"},{"issue":"2","key":"9510_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1137\/0123019","volume":"23","author":"M.R. Garey","year":"1972","unstructured":"Garey, M.R.: Optimal binary identification procedures. SIAM J. Appl. Math. 23(2), 173\u2013186 (1972). http:\/\/www.jstor.org\/stable\/2099637","journal-title":"SIAM J. Appl. Math."},{"key":"9510_CR7","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF00263588","volume":"3","author":"M.R. Garey","year":"1974","unstructured":"Garey, M.R., Graham, R.L.: Performance bounds on the splitting algorithm for binary testing. Acta Inform. 3, 347\u2013355 (1974)","journal-title":"Acta Inform."},{"key":"9510_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"issue":"2","key":"9510_CR9","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/inco.1996.0040","volume":"126","author":"T. Hancock","year":"1996","unstructured":"Hancock, T., Jiang, T., Li, M., Tromp, J.: Lower bounds on learning decision lists and trees. Inf. Comput. 126(2), 114\u2013122 (1996)","journal-title":"Inf. Comput."},{"key":"9510_CR10","unstructured":"Heeringa, B.: Improving access to organized information. Ph.D. thesis, University of Massachusetts, Amherst (2006)"},{"issue":"1","key":"9510_CR11","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":"9510_CR12","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"6th International Workshop on Algorithms and Data Structures","author":"S.R. Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Przytycka, T.M., Borgstrom, R.S.: On an optimal split tree problem. In: Dehne, F.K.H.A., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) 6th International Workshop on Algorithms and Data Structures, vol. 1663, pp. 157\u2013168 (1999)"},{"issue":"1\u20132","key":"9510_CR13","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.dam.2004.06.002","volume":"144","author":"E.S. Laber","year":"2004","unstructured":"Laber, E.S., Nogueira, L.T.: On the hardness of the minimum height decision tree problem. Discrete Appl. Math. 144(1\u20132), 209\u2013212 (2004). doi: 10.1016\/j.dam.2004.06.002","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9510_CR14","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1145\/356893.356898","volume":"14","author":"B.M.E. Moret","year":"1982","unstructured":"Moret, B.M.E.: Decision trees and diagrams. ACM Comput. Surv. 14(4), 593\u2013623 (1982). doi: 10.1145\/356893.356898","journal-title":"ACM Comput. Surv."},{"key":"9510_CR15","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-540-27794-1_7","volume-title":"Transactions on Rough Sets","author":"M.J. Moshkov","year":"2004","unstructured":"Moshkov, M.J.: Greedy algorithm of decision tree construction for real data tables. In: Transactions on Rough Sets, pp. 161\u2013168 (2004)"},{"key":"9510_CR16","first-page":"83","volume-title":"ICDT","author":"K. Munagala","year":"2005","unstructured":"Munagala, K., Babu, S., Motwani, R., Widom, J.: The pipelined set cover problem. In: ICDT, pp.\u00a083\u201398 (2005)"},{"key":"9510_CR17","unstructured":"Murthy, K.V.S.: On growing better decision trees from data. Ph.D. thesis, The Johns Hopkins University (1996)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9510-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9510-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9510-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9510-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,5]]},"references-count":17,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9510"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9510-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,5]]}}}