Minimization of decision trees is hard to approximate

@article{citeulike:2274241, 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 under the assumption P[not equal to]NP.}, author = {Sieling, Detlef }, booktitle = {Computational Complexity 2003}, citeulike-article-id = {2274241}, doi = {10.1016/j.jcss.2007.06.014}, journal = {Journal of Computer and System Sciences}, keywords = {algorithms, complexity, kdd, logic}, month = {May}, number = {3}, pages = {394--403}, posted-at = {2008-01-22 14:44:55}, priority = {2}, title = {Minimization of decision trees is hard to approximate}, url = {http://dx.doi.org/10.1016/j.jcss.2007.06.014}, volume = {74}, year = {2008} }

TY - JOUR ID - citeulike:2274241 L3 - citeulike-article-id:2274241 TI - Minimization of decision trees is hard to approximate T2 - Computational Complexity 2003 JF - Journal of Computer and System Sciences VL - 74 IS - 3 SP - 394 EP - 403 N2 - 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 under the assumption P[not equal to]NP. KW - algorithms KW - complexity KW - kdd KW - logic AU - Sieling, Detlef PY - 2008/05// UR - http://dx.doi.org/10.1016/j.jcss.2007.06.014 ER -