Constructing optimal binary decision trees is NP-complete

Cites Work

Reducibility among combinatorial problems
Optimal Binary Identification Procedures
The complexity of theorem-proving procedures
On the computational power of pushdown automata
Combining decision rules in a decision table
Conversion of limited-entry decision tables to computer programs

Cited In (only showing first 100 items - show all)

Recognizing polygonal parts width measurements
Learning optimal decision trees using constraint programming
Reduction of the number of particles in the stochastic weighted particle method for the Boltzmann equation
Decision-theoretic troubleshooting: hardness of approximation
Mathematical optimization in classification and regression trees
Efficient sequential decision-making algorithms for container inspection operations
Adaptive estimation of multivariate piecewise polynomials and bounded variation functions by optimal decision trees
Electronic circuit diagnostic expert systems - a survey
Discrete decision theory: manipulations
Sequential model-based diagnosis by systematic search
Balanced \(k\)-means clustering on an adiabatic quantum computer
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
On Polynomial Time Constructions of Minimum Height Decision Tree
An experimental evaluation of simplicity in rule learning
Learning decision trees with flexible constraints and objectives using integer optimization
Decision tree approximations of Boolean functions
Sequential testing of complex systems: a review
Profit driven decision trees for churn prediction
On Tackling Explanation Redundancy in Decision Trees
An improved test selection optimization model based on fault ambiguity group isolation and chaotic discrete PSO
Searching in random partially ordered sets
Stochastic tree search for estimating optimal dynamic treatment regimes
Solving feature subset selection problem by a parallel scatter search
Queries revisited.
Column generation based heuristic for learning classification trees
Sparsity in optimal randomized classification trees
Stochastic dynamic programming with factored representations
Decision Trees for Geometric Models
Exact learning from an honest teacher that answers membership queries
Optimization problems for machine learning: a survey
A study of search algorithms' optimization speed
bsnsing: A Decision Tree Induction Method Based on Recursive Optimal Boolean Rule Composition
On the complexity of approximating and illuminating three-dimensional convex polyhedra
A multi-tree committee to assist port-of-entry inspection decisions
Totally optimal decision trees for Boolean functions
Optimization and analysis of decision trees and rules: dynamic programming approach
Minimization of decision trees is hard to approximate
A note on the comparison of five heuristic optimization techniques of a certain class of decision trees
Inferring decision trees using the minimum description length principle
Supervised Deep Learning in High Energy Phenomenology: a Mini Review*
Inductive learning models with missing values
Optimal decision trees for feature based parameter tuning: integer programming model and VNS heuristic
Logical analysis of data: classification with justification
Optimal decision trees for the algorithm selection problem: integer programming based approaches
Improved approximation algorithms for the average-case tree searching problem
Hardness and inapproximability of minimizing adaptive distinguishing sequences
On the complexity of searching in trees and partially ordered structures
Optimal mistake bound learning is hard
The binary identification problem for weighted trees
Decision trees for function evaluation: simultaneous optimization of worst and expected cost
On the hardness of the minimum height decision tree problem
Point probe decision trees for geometric concept classes
Learning local transductions is hard
Approximations to clustering and subgraph problems on trees
Approximating optimal binary decision trees
Optimal survival trees
Multi-stage optimization of decision and inhibitory trees for decision tables with many-valued decisions
Learning multicriteria classification models from examples: decision rules in continuous space
Wrappers for feature subset selection
Computer science and decision theory
Bi-criteria optimization of decision trees with applications to data analysis
On sparse optimal regression trees
HHCART: an oblique decision tree
Performance bounds for binary testing with arbitrary weights
Optimal classification trees
Data science applications to string theory
\textsc{Treant}: training evasion-aware decision trees
A global search approach for inducing oblique decision trees using differential evolution
An improved column-generation-based matheuristic for learning classification trees
Optimal classification trees with leaf-branch and binary constraints
Supervised feature compression based on counterfactual analysis
Parallel construction of decision trees with consistently non-increasing expected number of tests
Synergies between machine learning and reasoning -- an introduction by the Kay R. Amel group
Title not available (Why is that?)
Optimal randomized classification trees
Finding small equivalent decision trees is hard
Optimal decision trees for categorical data via integer programming
Profinite Rigidity in the SnapPea Census
Loss-optimal classification trees: a generalized framework and the logistic case
On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods
Variation of critical point of aging transition in a networked oscillators system
SAT-based optimal classification trees for non-binary data
A framework for inherently interpretable optimization models
Modular learning models in forecasting natural phenomena.
Regularizing axis-aligned ensembles via data rotations that favor simpler learners
Classification via two-way comparisons (extended abstract)
On the difficulty of designing good classifiers
Margin optimal classification trees
Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
Title not available (Why is that?)
Decision trees based on 1-consequences
End-to-end learning of decision trees and forests
Chosen-ciphertext security from subset sum
On the Impact and Proper Use of Heuristics in Test-Driven Ontology Debugging
Decision trees unearth return sign predictability in the S\&P 500
Shattering inequalities for learning optimal decision trees
Interpretable machine learning: fundamental principles and 10 grand challenges
Supervised classification of curves via a combined use of functional data analysis and tree-based methods
Knowledge extraction with interval temporal logic decision trees
Theoretical Analysis of Git Bisect

This page was built for publication: Constructing optimal binary decision trees is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1228355)