On the hardness of the minimum height decision tree problem

DOI10.1016/j.dam.2004.06.002zbMath1078.68043OpenAlexW2008789644MaRDI QIDQ1885823

Loana Tito Nogueira, Eduardo Sany Laber

Publication date: 12 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.002

zbMATH Keywords

Computational complexityDecision treesAlgorithmical approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

On the tree search problem with non-uniform costs ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ Theoretical analysis of git bisect ⋮ Approximating optimal binary decision trees ⋮ An approximation algorithm for binary searching in trees ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Hardness and inapproximability of minimizing adaptive distinguishing sequences ⋮ The binary identification problem for weighted trees ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ Approximating decision trees with value dependent testing costs

Cites Work

• Constructing optimal binary decision trees is NP-complete
• A threshold of ln n for approximating set cover
• Decision Trees for Geometric Models
• Optimal Binary Identification Procedures
• Unnamed Item
• Unnamed Item

This page was built for publication: On the hardness of the minimum height decision tree problem