A simple approximation algorithm for optimal decision tree

DOI10.1016/J.ORL.2025.107370MaRDI QIDQ6847263zbMATH OpenFDO

Authors Zhengjia Zhuo, Viswanath Nagarajan

Publication date 9 March 2026

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ORL.2025.107370

zbMATH Keywords

active learningapproximation algorithmsoptimal decision tree

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
• Adaptive submodular ranking and routing
• Approximating Decision Trees with Multiway Branches
• Approximating optimal binary decision trees
• Approximation algorithms for optimal decision trees and adaptive TSP problems
• Average-case active learning with costs
• Constructing optimal binary decision trees is NP-complete
• Decision trees for entity identification, approximation algorithms and hardness results
• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• scientific article; zbMATH DE number 2185610 (Why is no real title available?)
• Minimum cost adaptive submodular cover
• On greedy algorithms for decision trees
• Performance bounds for binary testing with arbitrary weights
• Performance bounds on the splitting algorithm for binary testing

This page was built for publication: A simple approximation algorithm for optimal decision tree

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