# A Simple Approximation Algorithm for Optimal Decision Tree

arXiv: https://arxiv.org/abs/2505.15641 · HTML: https://mlsanity.com/paper/2505.15641/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 19 references that are in the map.
- First posted on arXiv 21 May 2025.

## Builds on (most cited first, 3 of 3)

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree](https://mlsanity.com/paper/1906.11385/) (2019)
- [Minimum Cost Adaptive Submodular Cover](https://mlsanity.com/paper/2208.08351/) (2022)

## Built on by (most cited first, 2 of 2)

- [Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover](https://mlsanity.com/paper/2604.12036/) (2026)
- [Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation](https://mlsanity.com/paper/2606.24672/) (2026)

## Abstract (arXiv)

Optimal decision tree (odt) is a fundamental problem arising in applications such as active learning, entity identification, and medical diagnosis. An instance of odt is given by m hypotheses, out of which an unknown ``true'' hypothesis is drawn according to some probability distribution. An algorithm needs to identify the true hypothesis by making queries: each query incurs a cost and has a known response for each hypothesis. The goal is to minimize the expected query cost to identify the true hypothesis. We consider the most general setting with arbitrary costs, probabilities and responses. odt is NP-hard to approximate better than ln m and there are O(ln m) approximation algorithms known for it. However, these algorithms and/or their analyses are quite complex. Moreover, the leading constant factors are large. We provide a simple algorithm and analysis for odt, proving an approximation ratio of 8 ln m.