{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:59:10Z","timestamp":1780639150733,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642175138","type":"print"},{"value":"9783642175145","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_18","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:09:23Z","timestamp":1291406963000},"page":"206-217","source":"Crossref","is-referenced-by-count":10,"title":["On Greedy Algorithms for Decision Trees"],"prefix":"10.1007","author":[{"given":"Ferdinando","family":"Cicalese","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tobias","family":"Jacobs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduardo","family":"Laber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Abrahams, J.: Code and parse trees for lossless source encoding. In: Compression and Complexity of Sequences 1997, pp. 145\u2013171 (1997)","DOI":"10.1109\/SEQUEN.1997.666911"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","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.\u00a05171, pp. 1\u20139. Springer, Heidelberg (2008)"},{"issue":"3","key":"18_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S0218195998000175","volume":"8","author":"E. Arkin","year":"1998","unstructured":"Arkin, E., Meijer, H., Mitchell, J., Rappaport, D., Skiena, S.: Decision trees for geometric models. International Journal of Computational Geometry and Applications\u00a08(3), 343\u2013364 (1998)","journal-title":"International Journal of Computational Geometry and Applications"},{"issue":"1","key":"18_CR4","doi-asserted-by":"publisher","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.: Searching in random partially ordered sets. Theoretical Computer Science\u00a0321(1), 41\u201357 (2004)","journal-title":"Theoretical Computer Science"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision trees for entity identification: Approximation algorithms and hardness results. In: PODS, pp. 53\u201362 (2007)","DOI":"10.1145\/1265530.1265538"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V., Pandit, V., Roy, S., Sabharwal, P.: Approximating decision trees with multiway branches. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 210\u2013221. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-02927-1_19"},{"key":"18_CR7","unstructured":"Dasgupta, S.: Analysis of a Greedy Active Learning Strategy. In: NIPS (2007)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Karp, R., Mossel, E., Riesenfeld, S., Verbin, E.: Sorting and selection in posets. In: SODA, pp. 392\u2013401 (2009)","DOI":"10.1137\/1.9781611973068.44"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Dereniowski, D., Kubale, M.: Efficient parallel query processing by graph ranking. Fundamenta Informaticae\u00a069 (2008)","DOI":"10.3233\/FUN-2006-69302"},{"issue":"13","key":"18_CR10","doi-asserted-by":"publisher","first-page":"2493","DOI":"10.1016\/j.dam.2008.03.007","volume":"156","author":"D. Dereniowski","year":"2008","unstructured":"Dereniowski, D.: Edge ranking and searching in partial orders. Discrete Applied Mathematics\u00a0156(13), 2493\u20132500 (2008)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"18_CR11","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1137\/0123019","volume":"23","author":"M. Garey","year":"1972","unstructured":"Garey, M.: Optimal binary identification procedures. SIAM Journal on Applied Mathematics\u00a023(2), 173\u2013186 (1972)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF00263588","volume":"3","author":"M. Garey","year":"1974","unstructured":"Garey, M., Graham, R.: Performance bounds on the splitting algorithm for binary testing. Acta Informatica\u00a03, 347\u2013355 (1974)","journal-title":"Acta Informatica"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Golin, M., Kenyon, C., Young, N.: Huffman coding with unequal letter costs. In: STOC, pp. 785\u2013791 (2002)","DOI":"10.1145\/509907.510020"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Guillory, A., Bilmes, J.: Average-Case Active Learning with Costs. In: The 20th Intl. Conference on Algorithmic Learning Theory (2009)","DOI":"10.1007\/978-3-642-04414-4_15"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Nagarajan, V., Ravi, R.: Approximation algorithms for optimal decision trees and adaptive TSP problems. In: ICALP (2010)","DOI":"10.1007\/978-3-642-14165-2_58"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"Hyafil, L., Rivest, R.: Constructing obtimal binary decision trees is NP-complete. Information Processing Letters\u00a05, 15\u201317 (1976)","journal-title":"Information Processing Letters"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Jacobs, T., Cicalese, F., Laber, E., Molinaro, M.: On the Complexity of Searching in Trees: Average-Case Minimization. In: ICALP (2010)","DOI":"10.1007\/978-3-642-14165-2_45"},{"issue":"6","key":"18_CR19","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1137\/0217076","volume":"17","author":"W. Knight","year":"1988","unstructured":"Knight, W.: Search in an ordered array having variable probe cost. SIAM Journal on Computing\u00a017(6), 1203\u20131214 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"D. Knuth","year":"1971","unstructured":"Knuth, D.: Optimum binary search trees. Acta. Informat.\u00a01, 14\u201325 (1971)","journal-title":"Acta. Informat."},{"key":"18_CR21","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":"R. Kosaraju","year":"1999","unstructured":"Kosaraju, R., Przytycka, T., Borgstrom, R.: On an optimal split tree problem. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 157\u2013168. Springer, Heidelberg (1999)"},{"key":"18_CR22","unstructured":"Laber, E., Milidi\u00fa, R., Pessoa, A.: On binary searching with non-uniform costs. In: SODA, pp. 855\u2013864 (2001)"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Laber, E., Molinaro, M.: An Approximation Algorithm for Binary Searching in Trees. Algorithmica, doi: 10.1007\/s00453-009-9325-0","DOI":"10.1007\/s00453-009-9325-0"},{"issue":"1-2","key":"18_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.dam.2004.06.002","volume":"144","author":"E. Laber","year":"2004","unstructured":"Laber, E., Nogueira, L.: On the hardness of the minimum height decision tree problem. Discrete Applied Mathematics\u00a0144(1-2), 209\u2013212 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/18.370098","volume":"41","author":"M. Lipman","year":"1995","unstructured":"Lipman, M., Abrahams, J.: Minimum average cost testing for partially ordered components. IEEE Transactions on Information Theory\u00a041, 287\u2013291 (1995)","journal-title":"IEEE Transactions on Information Theory"},{"key":"18_CR26","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: SODA, pp. 1096\u20131105 (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T12:13:29Z","timestamp":1740744809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}