TL;DR
This paper provides a breakthrough analysis of the classic greedy algorithm for the Uniform Decision Tree (UDT) problem, proving it achieves a tighter approximation ratio of $O(\frac{\log n}{\log C_{OPT}})$. Leveraging this, the authors introduce the first subexponential-time algorithm that achieves a constant-factor approximation for UDT, suggesting the problem is likely not NP-hard to approximate within super-constant factors.
What Problem Does This Paper Address?
The Decision Tree problem is a fundamental task in active learning and hypothesis testing. Given $n$ hypotheses and a set of tests, the goal is to build a decision tree that uniquely identifies each hypothesis while minimizing the average number of tests required (the average depth).
For the general version with non-uniform weights, the complexity is well-understood: the greedy algorithm gives an $O(\log n)$ approximation, and beating this is NP-hard. However, for the Uniform Decision Tree (UDT)—where every hypothesis is equally likely—a significant gap remained. While the best known polynomial-time algorithm (greedy) achieved $O(\log n)$, the best known hardness result was only $4 - \epsilon$.
This paper bridges that gap by asking: Can we do better than $O(\log n)$ for UDT, and just how hard is this problem really?
Methods
The authors employ two primary strategies: a novel analysis of the greedy algorithm and a hybrid subexponential-time algorithm.
- Tighter Greedy Analysis: The authors decompose the cost of the greedy tree by looking at its interior vertices. They categorize these vertices as either "balanced" (where the test splits the hypotheses relatively evenly) or "imbalanced."
- Balanced Vertices: Handled using an entropy argument, showing that these nodes efficiently reduce uncertainty.
- Imbalanced Vertices: The key innovation here is establishing a formal connection to the Min Sum Set Cover (MSSC) problem. By showing that chains of imbalanced vertices in a greedy decision tree correspond to greedy solutions for MSSC, they apply known constant-factor approximation bounds from the MSSC literature to the UDT setting.
- Subexponential Algorithm: The authors design an algorithm that switches strategies based on the performance of the greedy approach.
- If the greedy algorithm returns a "deep" tree, the new analysis proves it is already a good approximation.
- If the greedy tree is "shallow," the algorithm uses brute-force search to find the optimal tree up to a certain depth and then recurses. Because the depth is limited, this search runs in subexponential time $2^{\tilde{O}(n^\alpha)}$.
Datasets
Not discussed in the paper. This is a theoretical work focused on computational complexity and algorithm design; no empirical evaluation on specific datasets was performed.
Key Insights and Ideas
- The MSSC Connection: The most significant technical contribution is the "upper bound" connection between UDT and Min Sum Set Cover. Previously, only "lower bound" reductions (showing UDT is at least as hard as MSSC) were known.
- Resolving a Conjecture: The new analysis proves a 20-year-old conjecture by Kosaraju et al., confirming that the greedy algorithm's performance is indeed $O(\frac{\log n}{\log \log n})$ when the optimal cost is $O(\log n)$.
- Complexity Class Shift: By providing a subexponential algorithm for constant-factor approximations, the authors show that UDT belongs to a rare class of "intermediate" problems. Like Graph Isomorphism or Unique Games, it sits in a grey area: harder than typical polynomial-time problems, but likely not NP-hard in certain approximation regimes.
Key Results
The paper's findings are summarized in the complexity landscape shown in Figure 1:
- Greedy Performance: The greedy algorithm achieves an approximation ratio of $O(\frac{\log n}{\log C_{OPT}})$. The authors also prove this bound is tight—meaning you can't prove a better ratio for the greedy algorithm itself.
- Constant Approximation: For any $\alpha \in (0, 1)$, there exists a $\frac{9.01}{\alpha}$ approximation algorithm for UDT that runs in $2^{\tilde{O}(n^\alpha)}$ time.
- ETH Implications: Assuming the Exponential Time Hypothesis (which posits that 3-SAT cannot be solved in subexponential time), the existence of this algorithm implies that achieving any super-constant approximation ratio for UDT is not NP-hard.
Limitations and Future Work
- Hardness Gap: While the paper shows super-constant approximation isn't NP-hard, it doesn't settle whether a constant approximation (like a factor of 5 or 10) can be achieved in polynomial time. The gap between the $4-\epsilon$ hardness and the $O(\frac{\log n}{\log \log n})$ polynomial-time greedy bound remains.
- Non-Uniform Test Costs: The current work assumes all tests have equal cost. Extending these subexponential results to scenarios where tests have different costs is an open challenge.
- Fine-Grained Complexity: The authors suggest that future work could explore even tighter hardness results or faster algorithms for specific approximation ratios using fine-grained complexity analysis.
Summary updated