{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T07:43:15Z","timestamp":1768722195976,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642029264","type":"print"},{"value":"9783642029271","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_19","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"210-221","source":"Crossref","is-referenced-by-count":13,"title":["Approximating Decision Trees with Multiway Branches"],"prefix":"10.1007","author":[{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Vinayaka","family":"Pandit","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Yogish","family":"Sabharwal","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"19_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1009744630224","volume":"2","author":"S. Murthy","year":"1998","unstructured":"Murthy, S.: Automatic construction of decision trees from data: A multi-disciplinary survey. Data Mining and Knowledge Discovery\u00a02(4), 345\u2013389 (1998)","journal-title":"Data Mining and Knowledge Discovery"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1145\/356893.356898","volume":"14","author":"B. Moret","year":"1982","unstructured":"Moret, B.: Decision trees and diagrams. ACM Computing Surveys\u00a014(4), 593\u2013623 (1982)","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"19_CR3","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 optimal binary decision trees is NP-complete. Information Processing Letters\u00a05(1), 15\u201317 (1976)","journal-title":"Information Processing Letters"},{"issue":"2","key":"19_CR4","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":"19_CR5","doi-asserted-by":"crossref","unstructured":"Kosaraju, S., Przytycka, M., Borgstrom, R.: On an optimal split tree problem. In: Workshop on Algorithms and Data Structures (1999)","DOI":"10.1007\/3-540-48447-7_17"},{"key":"19_CR6","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)"},{"key":"19_CR7","unstructured":"Heeringa, B.: Improving Access to Organized Information. Ph.D. thesis, University of Massachusetts, Amherst (2006)"},{"key":"19_CR8","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":"19_CR9","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: ACM Symposium on Principles of Database Systems (2007)","DOI":"10.1145\/1265530.1265538"},{"issue":"4","key":"19_CR10","doi-asserted-by":"publisher","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\u00a040(4), 219\u2013234 (2004)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:53:30Z","timestamp":1558407210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}