NP-completeness of problems of construction of optimal decision trees

By G. Naumov. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Ş. Ertekin
2. Cynthia Rudin
3. Lior Rokach
4. Oded Z. Maimon
5. Sreerama K. Murthy
6. Berk Ustun
7. Tong Wang
8. Zhi Chen

Citations in the corpus

• Learning customized and optimized lists of rules with mathematical programming (2018, background): “The problem of finding an optimal decision tree is NP-hard [48], so classical methods do not aim to fully solve the problem to optimality.”
• Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey (1998, background): “Naumov [274] proved that optimal decision tree construction from decision tables is NP-complete under a variety of measures.”
• Top-down induction of decision trees classifiers - a survey (2005, methodology): “The last references indicate that using optimal decision tree algorithms is feasible only in small problems.”