# Precedence-Constrained Decision Trees and Coverings

arXiv: https://arxiv.org/abs/2602.21312 · HTML: https://mlsanity.com/paper/2602.21312/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 53 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 11 of 11)

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree](https://mlsanity.com/paper/1906.11385/) (2019)
- [Deterministic and Probabilistic Binary Search in Graphs](https://mlsanity.com/paper/1503.00805/) (2015)
- [Minimum Cost Adaptive Submodular Cover](https://mlsanity.com/paper/2208.08351/) (2022)
- [A General Framework for Robust Interactive Learning](https://mlsanity.com/paper/1710.05422/) (2017)
- [Noisy (Binary) Searching: Simple, Fast and Correct](https://mlsanity.com/paper/2107.05753/) (2021)
- [Approximation Strategies for Generalized Binary Search in Weighted Trees](https://mlsanity.com/paper/1702.08207/) (2017)
- [Competitive Online Search Trees on Trees](https://mlsanity.com/paper/1908.00848/) (2019)
- [On the Tree Search Problem with Non-uniform Costs](https://mlsanity.com/paper/1404.4504/) (2014)
- [Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees](https://mlsanity.com/paper/2402.05560/) (2024)
- [Approximating the Average-Case Graph Search Problem with Non-Uniform Costs](https://mlsanity.com/paper/2511.06564/) (2025)

## Built on by (most cited first, 1 of 1)

- [Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs](https://mlsanity.com/paper/2607.13217/) (2026)

## Abstract (arXiv)

This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover. We study these two fundamental tasks under precedence constraints, that is, if a test (or set) X is a predecessor of Y, then in any feasible decision tree X needs to be an ancestor of Y (or respectively, if Y is added to set cover, then so must be X). For the Optimal Decision Tree we consider two optimization criteria: worst case identification time (height of the tree) or the average identification time. Similarly, for the Set Cover we study two cost measures: the size of the cover or the average cover time. Our approach is to develop a number of algorithmic reductions, where an approximation algorithm for one problem provides an approximation for another via a black-box usage of a procedure for the former. En route we introduce other optimization problems either to complete the `reduction landscape' or because they hold the essence of combinatorial structure of our problems. The latter is brought by a problem of finding a Maximum Density Precedence-Closed Subfamily, where the density is defined as the ratio of the number of items the family covers to its size. We provide O^*(√m)-approximation polynomial-time algorithms for all aforementioned problems. The picture is complemented by a number of hardness reductions that provide O(m1/12-ε)-inapproximability results for the decision tree and covering problems. Besides giving a complete set of results for general precedence constraints, we also provide polylogarithmic approximation guarantees for two most typically studied and applicable graph types, outforests and inforests. By providing corresponding hardness results, we show most of these results to be tight.