Minimization of decision trees is hard to approximate

DOI10.1016/J.JCSS.2007.06.014zbMath1133.68025OpenAlexW2026324637MaRDI QIDQ2475411

Detlef Sieling

Publication date: 11 March 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.014

zbMATH Keywords

decision treenonapproximability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

New degree bounds for polynomial threshold functions ⋮ Correlation based splitting criterionin multi branch decision tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Constructing optimal binary decision trees is NP-complete
• Some APX-completeness results for cubic graphs
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Exact learning when irrelevant variables abound
• The complexity of minimizing and learning OBDDs and FBDDs
• Learning decision trees from random examples
• Complexity measures and decision tree complexity: a survey.
• The nonapproximability of OBDD minimization
• Lower bounds on learning decision lists and trees
• Branching Programs and Binary Decision Diagrams
• FINDING SMALL EQUIVALENT DECISION TREES IS HARD
• Finding the optimal variable ordering for binary decision diagrams

This page was built for publication: Minimization of decision trees is hard to approximate