論文の概要: Constant-Factor Approximation for the Uniform Decision Tree

• arxiv url: http://arxiv.org/abs/2604.12036v1
• Date: Mon, 13 Apr 2026 20:24:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.112562
• Title: Constant-Factor Approximation for the Uniform Decision Tree
• Title（参考訳）: 一様決定木に対する定数因子近似
• Authors: Michał Szyfelbein,
• Abstract要約: 我々はtextsc Clustering [SODA '17, WALCOM '26] に関連する問題から知られている分解手法を用いて、最適な決定木をサブファミリと呼ばれる一連のオブジェクトに分解する。 我々は,テキスト分離サブファミリー問題に対する優れた近似を求め,元の問題に対する近似アルゴリズムの設計を可能にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We resolve a long-standing open question, about the existence of a constant-factor approximation algorithm for the average-case \textsc{Decision Tree} problem with uniform probability distribution over the hypotheses. We answer the question in the affirmative by providing a simple polynomial-time algorithm with approximation ratio of $\frac{2}{1-\sqrt{(e+1)/(2e)}}+ε<11.57$. This improves upon the currently best-known, greedy algorithm which achieves $O(\log n/{\log\log n})$-approximation. The first key ingredient in our analysis is the usage of a decomposition technique known from problems related to \textsc{Hierarchical Clustering} [SODA '17, WALCOM '26], which allows us to decompose the optimal decision tree into a series of objects called separating subfamilies. The second crucial idea is to reduce the subproblem of finding a \textsc{Separating Subfamily} to an instance of the \textsc{Maximum Coverage} problem. To do so, we analyze the properties of cutting cliques into small pieces, which represent pairs of hypotheses to be separated. This allows us to obtain a good approximation for the \textsc{Separating Subfamily} problem, which then enables the design of the approximation algorithm for the original problem.
• Abstract（参考訳）: 我々は、仮説上の一様確率分布を持つ平均ケース \textsc{Decision Tree} 問題に対する定数係数近似アルゴリズムの存在について、長年の未解決問題を解決する。 近似比が $\frac{2}{1-\sqrt{(e+1)/(2e)}}+ε<11.57$ の単純な多項式時間アルゴリズムを提供することで、肯定的な質問に答える。 これにより、現在最もよく知られているgreedyアルゴリズムが$O(\log n/{\log\log n})$-approximationを達成する。 分析における第1の要素は, <textsc{Hierarchical Clustering} [SODA '17, WALCOM '26] に関連する問題から知られている分解手法を使用することで, 最適決定木を分離サブファミリと呼ばれる一連のオブジェクトに分解することができる。 2つ目の重要な考え方は、 \textsc{Separating Sub Family} を見つけるサブプロブレムを \textsc{Maximum Coverage} 問題のインスタンスに還元することである。 そこで我々は, 分離すべき仮説の対を表す小片に断面を切断する特性を解析した。 これにより、 \textsc{Separating Sub Family} 問題に対する適切な近似が得られ、元の問題に対する近似アルゴリズムの設計が可能になる。

関連論文リスト

• Precedence-Constrained Decision Trees and Coverings [0.8594140167290095]
  この研究は、多くの最適化問題とそれらの間の還元的関係を考察する。 私たちが関心を持っている主な問題は、emph Optimal Decision TreeとemphSet Coverの2つです。
  論文  参考訳（メタデータ） (2026-02-24T19:33:36Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  本研究では,有限状態空間を持つ無限水平割引決定過程(MD)に対して,単時間アクタークリティカル(AC)アルゴリズムのグローバル収束を解析する。 我々は,アクタと批評家の両方のステップサイズが (O(k-Pfrac12) として崩壊し,従来の (O(k-Pfrac12) ) レートから (非最適) の Markov フレームワーク最適化で一般的に使用される (O(k-Pfrac12) ) レートから$k$ になることを示した。
  論文  参考訳（メタデータ） (2024-10-11T14:46:29Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
  論文  参考訳（メタデータ） (2023-12-14T17:31:38Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。