Constant-Factor Approximation for the Uniform Decision Tree

We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case $\text{textsc}DecisionTree$ 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)\mathrm{/}(2e)}}+\epsilon <11.57$. This improves upon the currently best-known, greedy algorithm which achieves $O(\log n\mathrm{/}\log \log n)$-approximation. The first key ingredient in our analysis is the usage of a decomposition technique known from problems related to $\text{textsc}HierarchicalClustering$ [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 $\text{textsc}SeparatingSubfamily$ to an instance of the $\text{textsc}MaximumCoverage$ 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 $\text{textsc}SeparatingSubfamily$ problem, which then enables the design of the approximation algorithm for the original problem.