Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-054 | 5th September 2002 00:00

Minimization of Decision Trees is Hard to Approximate

RSS-Feed




TR02-054
Authors: Detlef Sieling
Publication: 18th September 2002 12:35
Downloads: 1524
Keywords: 


Abstract:

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown to be even hard to approximate up to any constant factor.



ISSN 1433-8092 | Imprint