![[2602.21312] Precedence-Constrained Decision Trees and Coverings](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.21312] Precedence-Constrained Decision Trees and Coverings
Summary
This paper explores optimization problems related to precedence-constrained decision trees and set coverings, presenting new approximation algorithms and hardness results.
Why It Matters
The findings enhance our understanding of decision-making processes in computational settings, particularly in machine learning and algorithm design. By addressing precedence constraints, the research has implications for improving efficiency in various applications, such as data classification and resource allocation.
Key Takeaways
- Introduces precedence constraints in decision trees and set cover problems.
- Develops approximation algorithms with improved performance guarantees.
- Presents hardness results that indicate limits on approximation capabilities.
- Explores combinatorial structures relevant to optimization problems.
- Provides insights into specific precedence types like outforests and inforests.
Computer Science > Data Structures and Algorithms arXiv:2602.21312 (cs) [Submitted on 24 Feb 2026] Title:Precedence-Constrained Decision Trees and Coverings Authors:Michał Szyfelbein, Dariusz Dereniowski View a PDF of the paper titled Precedence-Constrained Decision Trees and Coverings, by Micha{\l} Szyfelbein and 1 other authors View PDF Abstract:This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the \emph{Optimal Decision Tree} and \emph{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 max...
