論文の概要: Precedence-Constrained Decision Trees and Coverings
- arxiv url: http://arxiv.org/abs/2602.21312v1
- Date: Tue, 24 Feb 2026 19:33:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-26 18:19:16.584274
- Title: Precedence-Constrained Decision Trees and Coverings
- Title（参考訳）: 順に制約された決定木と被覆
- Authors: Michał Szyfelbein, Dariusz Dereniowski,
- Abstract要約: この研究は、多くの最適化問題とそれらの間の還元的関係を考察する。
私たちが関心を持っている主な問題は、emph Optimal Decision TreeとemphSet Coverの2つです。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: この研究は、多くの最適化問題とそれらの間の還元的関係を考察する。
私たちが関心を持っている主な問題は、 \emph{Optimal Decision Tree} と \emph{Set Cover} の2つです。
テスト(または集合)$X$が$Y$の前身であるなら、任意の可能な決定木において$X$は$Y$の祖先である必要がある(あるいは、セットカバーに$Y$が加わった場合、$X$でなければならない)。
最適決定木については、最悪のケース識別時間(木の高さ)と平均識別時間という2つの最適化基準を検討する。
同様に、セットカバーについては、カバーのサイズと平均カバータイムの2つのコスト尺度について検討する。
提案手法は,ある問題に対する近似アルゴリズムが,前者の手順をブラックボックスでブラックボックスで近似するアルゴリズムを多数開発することである。
その過程で,「還元景観」を完遂する最適化問題や,それらが我々の問題の組合せ構造の本質を持っているため,他の最適化問題も導入する。
後者は、最大密度が閉部分群に先行する問題によって引き起こされ、その密度は、その家族がカバーするアイテムの数とそのサイズに対する比率として定義される。
これにより、上記のすべての問題に対して$\cO^*(\sqrt{m})$-approximationアルゴリズムを提供する。
この図は、決定木と問題をカバーするために$o(m^{1/12-ε})$-inapproximability結果を提供するいくつかの硬度減少によって補完される。
一般的な優先制約に対する完全な結果のセットに加えて、最もよく研究され、適用可能な2つの優先型、森林およびインフォレストに対して、多変数近似の保証も提供する。
対応する硬度結果を提供することで,これらの結果がきついことを示す。
関連論文リスト
- Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices [0.15469452301122175]
Multimarginal Schr"odinger Bridge (MSB) は、既知の統計と既知の相関構造を持つランダムベクトルの集合の最適結合を見つける。
最適MSBの計算は、測定値の頂点上での最小分散木問題の解に相当することがわかった。
論文 参考訳（メタデータ） (2025-09-12T18:15:42Z) - Superconstant Inapproximability of Decision Tree Learning [7.420043502440765]
PAC学習決定木をクエリで適切に学習する作業について検討する。
Koch, Strassle, および Tan の最近の研究は、仮説木 $T$ が最適に小さいことが要求されるこのタスクの最も厳密なバージョンは NP-hard であることを示した。
仮に$T$が最適の任意の定数係数の範囲内にあるとしても、そのタスクはNPハードのままであることを示す。
論文 参考訳（メタデータ） (2024-07-01T15:53:03Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文 参考訳（メタデータ） (2022-10-12T16:25:48Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。