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

DevFeed: [Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover](<https://devfeed.tech/articles/simpler-logarithmic-approximation-algorithms-for-the-optimal-decision-tree-and-adaptive-set-cover-94119.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2604.12036>)

Author: Micha{\\l} Szyfelbein

Published: 2026-10-21T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [set-cover](<https://devfeed.tech/tags/set-cover.md>)

## AI overview

The paper presents a greedy algorithm for the Optimal Decision Tree problem with a simplified analysis and simultaneous approximation factors below 3.65 log₂ n for worst-case cost and 7.3 log₂ n for average-case cost, where n is the number of hypotheses. It introduces Separating Subfamily, which selects a cheapest set of tests that partitions hypotheses into sufficiently small groups, and reduces that problem to Maximum Coverage. The approach uses properties of cutting a clique into small pieces, with edges representing hypothesis pairs to separate. The paper also applies ODT to Adaptive Set Cover, giving an O(log(k-n))-approximation, where k is the number of possible realizations.

## Source excerpt

arXiv:2604.12036v4 Announce Type: replace-cross 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 $\mathcal{O}(\log 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\log_2 n$ for worst-case cost and $7.3\log_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 $\mathcal{O}(\log (k\cdot n))$-approximation for the Adaptive Set Cover problem, where $k$ is the number of possible realizations.