Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover

arXiv:2604.12036 · cs.DS, cs.IR, cs.LG · Submitted 2026-04-13 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Hi, I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover".

Jane: Here's the gist of the paper. The gist: We show a new algorithm with a simplified analysis which simultaneously achieves an O(log n)-approximation for both cost criteria for both cost criteria.

Tom: Optimal Decision Tree Approximation The Optimal Decision Tree problem involves constructing a decision tree to identify an unknown target hypothesis from a ground set of hypotheses under either the average- and worst-case cost criteria.

Jane: The paper introduces a new greedy algorithm that selects a subfamily of tests rather than a single one, aiming to pay O(OPT) to split the hypotheses into relatively small subsets and recurse on each subset, leading to an O(log n)-approximation ratio for both objectives.

Tom: This approach is based on exploiting properties of cutting a clique into small pieces where edges represent pairs of hypotheses to be separated.

Title and authors: Tom: Let's talk about who wrote this. It's Michał Szyfelbein, and it was published on August twelve two thousand twenty-six in "Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover <ref:2604.12036#pg1,Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set>."

Jane: The title suggests they are focusing on making the approximation algorithms for both the Optimal Decision Tree and Adaptive Set Cover much simpler to understand. It's about showing a way to get O(log n) approximations without all that heavy technical machinery in the analysis.

Lu: The authors are reaching for a simpler path, moving away from overly complex proofs in their literature. They are specifically addressing how the structure of the problem lets them use a greedy choice that works well for both worst-case and average-case depth measures simultaneously.

Meng: I’m curious about what this simplification actually means for production systems. Does it mean we can build these decision trees faster or with less computational overhead when making real-time decisions?

Lalam: The core idea is that their greedy algorithm behaves in a certain way relative to the Separating Subfamily problem, and they use that property to guide the test selection process. It connects the ODT problem directly to this subproblem.

The paper's summary: Tom: So, what's the main gist here? They introduce a new greedy algorithm for the Optimal Decision Tree that achieves an O(log n)-approximation for both worst-case and average-case cost, and they have a really clean analysis behind it.

Jane: Essentially, they are showing that by focusing on selecting a subfamily of tests instead of just one single test, you can split the hypotheses into smaller groups in a way that keeps the overall cost low. They are leveraging properties related to cutting a clique into small pieces where edges represent pairs of hypotheses needing separation.

Lu: The paper reduces the Separating Subfamily problem to Maximum Coverage, and they show that this reduction helps them get an approximation algorithm for the Separating Subfamily itself. Theorem three proves there's a bicriteria one + delta, sqrt(one - (one - one/e) * (one - f))f-approximate FPTAS for the Separating Subfamily <ref:2604.12036#pg2>.

Meng: A FPTAS sounds complicated to implement, but if it gives you a solid approximation bound related to Maximum Coverage, that's useful for bounding things in practice. But what about the actual complexity of running this on a massive set of hypotheses?

Lalam: They construct the decision tree implicitly through a depth-first traversal of the recursion tree for all possible outcomes. This structure is what allows them to bound the cost by relating it back to OPTW (I) and OPTA(I), which are lower bounds based on separating subfamilies.

The paper's improvements: Tom: So, what are the specific improvements they're highlighting beyond just getting the O(log n) bound? They focus on how this new algorithm works compared to existing methods.

Jane: They are emphasizing that their greedy approach is directly related to a naturally defined subproblem, which is why it works for both quality measures at the same time. Most other heuristics might only handle one of them well, but this one handles both.

Lu: The authors show that they can combine the algorithms for average-case and worst-case cost to achieve asymptotically the same approximation guarantees for both quality measures, which is a nice property to have in a single algorithm.

Meng: If we're looking at deployment, combining the bounds is great because it means we don't have to run two separate procedures for different scenarios; one approach covers everything. But does this combination introduce any hidden dependencies on the input structure?

Lalam: The paper also shows how they can use this ODT result to get an O(log(k · n))-approximation for the Adaptive Set Cover problem by splitting it into two phases: identification and covering. This is where the real practical utility comes in.

Conclusion: Tom: So to wrap up, this paper delivers a simple greedy algorithm for the Optimal Decision Tree that gives us an O(log n) approximation for both worst-case and average-case cost, with constants under three point six five and twice as much for the average case, assuming base two logarithm <ref:2604.12036#pg1,and twice as much for the average case>.

Jane: That means we have a reliable way to build decision trees that don't just give one type of quality measure but two good ones simultaneously, which is a big deal for robust hypothesis testing. And they connect this to Adaptive Set Cover with an O(log(k · n)) approximation.

Lu: The main implication is the explicit construction for Adaptive Set Cover, where k is the number of possible realizations and n relates to component size, giving us transparent bounds on how good the resulting decision tree will be.

Meng: From a deployment standpoint, this transparency in k and n is helpful because it gives us a clear picture of what to expect when we run the system at scale. We can estimate the cost based on those parameters without needing to know every detail of the input data structure.

Lalam: The paper also highlights that there's hardness results showing that certain approximation guarantees for related problems, like Separating Subfamily and Set Cover, are hard to achieve unless P equals NP.

Tom: So in short, it’s a new way to get a simple O(log n) approximation for the Optimal Decision Tree on both cost criteria without overly technical analysis.

Jane: It’s a solid result that provides explicit bounds and shows how this specific structure of the problem allows us to handle multiple objectives at once with good performance. That's what we have here from "Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover."

Michaś Szyfelbein

cs.DS, cs.IR, cs.LG

Submitted: 2026-04-13

Updated: 2026-10-19

Comments: 21 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist: We show a new algorithm with a simplified analysis which simultaneously achieves an O(log n)-approximation for both cost criteria for both cost criteria.

Key concepts

Optimal Decision Tree (ODT): This problem involves building a decision tree to find an unknown target hypothesis from a set of possibilities. The goal is to minimize the total cost of the tests performed by the tree, considering either average or worst-case scenarios.
Separating Subfamily: This is a core technical problem related to finding a small collection of tests that can distinguish between all pairs of hypotheses in a set. The paper shows how to approximate this problem efficiently using reductions to Maximum Coverage.
Adaptive Set Cover: This is an application where the ODT result is used. It involves two phases: first, identifying the correct underlying scenario (realization) using an ODT approximation, and second, covering that scenario efficiently using a greedy Set Cover approach.

Terminology

Core — 1× in this paper · explained in 2 episodes

Summary

The gist: We show a new algorithm with a simplified analysis which simultaneously achieves an O(log n)-approximation for both cost criteria for both cost criteria.

Optimal Decision Tree Approximation

The Optimal Decision Tree problem involves constructing a decision tree to identify an unknown target hypothesis from a ground set of hypotheses under either the average- and worst-case cost criteria. The paper introduces a new greedy algorithm that selects a subfamily of tests rather than a single one, aiming to pay O(OPT) to split the hypotheses into relatively small subsets and recurse on each subset, leading to an O(log n)-approximation ratio for both objectives. This approach is based on exploiting properties of cutting a clique into small pieces where edges represent pairs of hypotheses to be separated. The analysis relies on reducing the Separating Subfamily problem to an instance of the well-known Maximum Coverage problem.

Separating Subfamily and Maximum Coverage Reduction

The core technical contribution involves obtaining a constant-factor approximation algorithm for the Separating Subfamily, which is reduced to the Maximum Coverage problem. The reduction exploits properties of partitioning a clique into small pieces, where edges represent pairs of hypotheses that need to be separated. A bicriteria (α, β)-approximation algorithm for the Separating Subfamily is shown to exist with a complexity related to the Maximum Coverage problem. Specifically, Theorem 3 proves the existence of a bicriteria 1 + δ, √1−(1−1/e)·(1−f)f-approximate FPTAS for the Separating Subfamily.

Decision Tree Construction and Cost Bounds

The algorithm constructs a decision tree D implicitly by performing a depth-first traversal of the recursion tree for all possible outcomes of the tests. Theorem 1 establishes that costW (D) ≤ α · log2/β n · OPTW (I) and costA(D) ≤ 2α · log2/β n · OPTA (I) for an instance I = (H, T, c) of the Optimal Decision Tree problem. The proof proceeds by establishing lower bounds on OPTW (I) and OPTA(I), relating them to separating subfamilies, and then using the approximation algorithm for the Separating Subfamily to bound the resulting cost.

Adaptive Set Cover Application

The paper provides an O(log(k · n))-approximation algorithm for the Adaptive Set Cover problem. This is achieved by reducing Adaptive Set Cover to a combination of Optimal Decision Tree and Set Cover. The process involves two phases: Phase 1, Identification, runs a (bicriteria) O(logH)-approximation algorithm for the ODT on an instance IODT where the set of hypotheses is H = R with the weight function w. Phase 2, Covering, runs an O(logU) approximation algorithm for Set Cover on the instance IR = (U = R, S, c). The resulting decision tree D is constructed by replacing internal nodes with sets/tests from the covering solution CR. Lemma 10 proves that the resulting decision tree D satisfies costA(D) ≤ O(log(k · n)) · OPTA ASC(I) and costW (D) ≤ O(log(k · n)) · OPTW ASC(I), leading to the final approximation guarantee.

Conclusion and Complexity

The resulting algorithm achieves a worst-case cost of below 3.65 for the Optimal Decision Tree problem and twice as much for the average-case cost, assuming base 2 logarithm. The adaptive set cover result yields an O(log(k · n))-approximation, where k is the number of possible realizations. This result is significant as it provides an explicit construction for Adaptive Set Cover that is bicriteria and has a transparent dependence on both k and n in the approximation ratio. The paper also demonstrates a hardness result showing that no ((1 − o(1)) · ln(n/2), 1) nor (1, 1 + 1/e − ε)-approximation algorithm exists for the Separating Subfamily unless P = NP.

Application Summary

The paper demonstrates how to leverage the ODT result to get an O(log(k · n))-approximation for Adaptive Set Cover. This is achieved by running a (bicriteria) O(logH)-approximation algorithm for the ODT on the set of hypotheses H = R with weight function w in Phase 1, and then using an O(logU) approximation algorithm for Set Cover on the instance IR = (U = R, S, c) in Phase 2. This combined strategy yields a decision tree D that is feasible for Realization Identification and results in cost bounds of O(log(k · n)) · OPTA ASC(I) and O(log(k · n)) · OPTW ASC(I). The overall algorithm is polynomial time, as the number of guesses for the budget B is at most O log1+δ c(T).

Final Result Summary

Corollary 7 states that for an appropriate choice of δ > 0, say δ = 10−4, there exists a polynomialtime algorithm that constructs a decision tree D such that costW (D) ≤ (1 + δ) · log n logq 2·e e+1 · OPTW (I) ≤ 3.65 · log n OPTW (I) and costA(D) ≤ 2 · (1 + δ) · log n logq 2·e e+1 · OPTA (I) ≤ 7.3 · log n OPTA (I). This demonstrates that the algorithm achieves a logarithmic approximation for both the worst-case and average-case cost objectives simultaneously. The main disadvantage noted is that these procedures were proven to achieve a logarithmic approximation only for only one of the two criterions, although they can be transformed into a bicriteria guaranteeing strategy.

Hardness Result Summary

Theorem 11 proves that there is no ((1 − o(1)) · ln(n/2), 1) nor (1, 1 + 1/e − ε)-approximation algorithm for the Separating Subfamily for any epsilon > 0, unless P = NP. This hardness result is derived by reducing from the Maximum Coverage problem and shows that obtaining a (1, 1 + 1/e − ε)-approximation guarantee is hard as well.

Set Cover Hardness Summary

Theorem 11 also implies that there is no ((− o(1)) · ln(n/2), 1) approximation algorithm for the Set Cover instance, unless P = NP. This hardness result is derived by reducing from a uniform-cost Maximum Coverage instance IMC and shows that obtaining a (1, 1 + 1/e − ε)-approximation guarantee is hard as well.

Final Conclusion Summary

The paper presents a simple greedy algorithm for the Optimal Decision Tree problem that simultaneously achieves an O(log n)-approximation for both the worst-case and average-case cost objectives. The algorithm has a relatively small constant under the O-notation, which is below 3.65 for the worst-case cost and twice as much for the average-case cost, assuming base 2 logarithm. We have also shown how to leverage this result in order to get an O(log(k · n))-approximation for the Adaptive Set Cover. The advantage of our simple approach is that the dependence on both k and n in the approximation ratio is transparent. The paper leaves as an open question whether one can improve this guarantee down to O(log r), or alternatively establish an inapproximability result excluding such a possibility. We also note that even if there existed a bicriteria constant-factor approximation algorithm for the generalization of the Separating Subfamily problem, our approach would only yield an O(log 1/pmin)-approximation for the average-case cost ODT, where pmin is the minimum probability among all of the hypotheses. The paper also answers whether it is possible to give a true, single-criteria, constant-factor approximation for the Separating Subfamily by showing that it generalizes Set Cover.

Final Summary

Improvements for AI systems

Adaptive Hypothesis Identification for System Faults: The improved system can perform adaptive testing to identify a hidden failure scenario from a set of possible scenarios with associated probabilities, minimizing expected cost. This is achieved by using the ODT algorithm on an instance where hypotheses are realizations and tests are sets/tests.
Efficient Search for Hidden Scenarios: The system can efficiently search through possible failure scenarios to find the hidden one by leveraging the ODT approximation guarantee of O(log k n) for Adaptive Set Cover, where k is the number of possible realizations and n is related to component size.
Optimized Component Repair Strategy: The improved system can design a sequential testing strategy that minimizes expected cost for fixing faulty components in a system, by combining an ODT-based identification phase with a greedy Set Cover phase on the identified realization.

Abstract

We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tree (ODT) problem has been extensively studied in the literature, and O(n) -approximation guarantees are known for each criterion, including a simultaneous guarantee for both (here n is the number of hypotheses) [ICML]. Although most of the existing algorithm use simple greedy strategies, their analyses rely on intricate arguments. Since ODT is a fundamental problem with wide-ranging applications, we are interested in developing algorithms that are both effective and easy to understand. We present a new greedy algorithm with a simplified analysis that simultaneously achieves approximation factors below 3.65 2 n for worst-case cost and 7.3 2 n for average-case cost. Our algorithm for the Optimal Decision Tree behaves greedily with respect to the hereby introduced Separating Subfamily problem which asks for the cheapest subfamily of tests which partitions the hypotheses into pieces of small enough size. We show that the Separating Subfamily can itself be reduced to an instance of the well-known Maximum Coverage problem. At the core of our approach lies exploiting properties of cutting a clique into small pieces, where edges represent pairs of hypotheses to be separated. In the spirit of simplicity, we also provide a new and straightforward application of ODT: an O((k times n)) -approximation for the Adaptive Set Cover problem, where k is the number of possible realizations.