Research
Constant-Factor Approximation for the Uniform Decision Tree
arXiv:2604.12036v1 Announce Type: cross Abstract: We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case extsc{Decision Tree} p
arXiv:2604.12036v1 Announce Type: cross Abstract: We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case extsc{Decision Tree} problem with uniform probability distribution over the hypotheses. We answer the question in the affirmative by providing a simple polynomial-time algorithm with approximation ratio of frac{2}{1-sqrt{(e+1)/(2e)}}+epsilon <11.57. This improves upon the currently best-known, greedy algorithm which achieves O(log n/{loglog n})-approximation. The first key ingredient in our analysis is the usage of a decomposition technique known from problems related to extsc{Hierarchical Clustering} [SODA '17, WALCOM '26], which allows us to decompose the optimal decision tree into a series of objects called separating subfamilies. The second crucial idea is to reduce the subproblem of finding a extsc{Separating Subfamily} to an instance of the extsc{Maximum Coverage} problem. To do so, we analyze the properties of cutting cliques into small pieces, which represent pairs of hypotheses to be separated. This allows us to obtain a good approximation for the extsc{Separating Subfamily} problem, which then enables the design of the approximation algorithm for the original problem.
Related
- WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees
- Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem
- Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent
- Gaussian Approximation for Asynchronous Q-learning
Source: arXiv cs.LG | 2026-04-15