Title :
Minimization of decision trees is hard to approximate
Author_Institution :
Dept. of Comput. Sci., RWTH, Aachen, Germany
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. The problem is even hard to approximate up to any constant factor.
Keywords :
Boolean functions; binary decision diagrams; computability; computational complexity; data mining; decision trees; minimisation; polynomial approximation; BDD; Boolean function; NP-hard; binary decision diagram; complexity theory; data exploration; data mining; decision tree minimization; discrete function; polynomial time approximation; satisfiability problem; Application software; Biology computing; Boolean functions; Chromium; Complexity theory; Computer science; Data mining; Decision trees; Input variables; Size measurement;
Conference_Titel :
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
Print_ISBN :
0-7695-1879-6
DOI :
10.1109/CCC.2003.1214412
