Precedence-Constrained Decision Trees and Coverings

• URL: http://arxiv.org/abs/2602.21312v1
• Date: Tue, 24 Feb 2026 19:33:36 GMT
• Title: Precedence-Constrained Decision Trees and Coverings
• Authors: Michał Szyfelbein, Dariusz Dereniowski,
• Abstract summary: This work considers a number of optimization problems and reductive relations between them.<n>The two main problems we are interested in are the emph Optimal Decision Tree and emphSet Cover.
• Score: 0.8594140167290095
• License: http://creativecommons.org/licenses/by/4.0/
• 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 maximum density precedence closed subfamily, where the density is defined as the ratio of the number of items the family covers to its size. By doing so we provide $\cO^*(\sqrt{m})$-approximation algorithms for all of the aforementioned problems. The picture is complemented by a number of hardness reductions that provide $o(m^{1/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 precedence types, outforests and inforests. By providing corresponding hardness results, we show these results to be tight.

Related papers

• Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion [8.063077447427451]
  We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space.<n>One of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and $(2+1)$ for metric MST to 2 and $2$ respectively.
  arXiv  Detail & Related papers  (2026-02-27T17:58:45Z)
• Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices [0.15469452301122175]
  The Multimarginal Schr"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure.<n>We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices.
  arXiv  Detail & Related papers  (2025-09-12T18:15:42Z)
• Superconstant Inapproximability of Decision Tree Learning [7.420043502440765]
  We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree $T$ is required to be optimally small, is NP-hard. We show that the task indeed remains NP-hard even if $T$ is allowed to be within any constant factor of optimal.
  arXiv  Detail & Related papers  (2024-07-01T15:53:03Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  We improve the approximation factor of the fastest deterministic algorithm from $6+epsilon$ to $5+epsilon$. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions.
  arXiv  Detail & Related papers  (2024-05-20T02:24:58Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem. We show that all used solvers perform very badly on a large majority of the instances. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
  arXiv  Detail & Related papers  (2023-06-29T14:57:56Z)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  Random forests and, more generally, (decisionnobreakdash-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute decision trees that are optimal for various measures such as their size or depth. We provide two novel algorithms and corresponding lower bounds.
  arXiv  Detail & Related papers  (2023-06-07T13:30:43Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  We prove, under randomized ETH, superpolynomial lower bounds for two basic problems. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees. We show our lower bound for learning decision trees can be improved to $nOmega(log s)$.
  arXiv  Detail & Related papers  (2022-10-12T16:25:48Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.