English(EN) Constant-Factor Approximation for the Uniform Decision Tree

决策树近似研究在投稿后被撤回

作者 PulseAugur 编辑部 · [1 个来源] · 2026-04-29 04:00

一篇最近被撤回的 arXiv 论文提出了一种用于近似 Uniform Decision Tree 问题的多项式时间算法。该算法实现了小于 11.57 的近似比，优于之前的贪心方法。其方法包括使用层次聚类技术分解最优决策树，并将子问题归约到最大覆盖问题。 AI

影响这项研究虽然被撤回，但探索了与人工智能决策过程相关的算法改进。

排序理由该集群包含一篇详细介绍新算法方法的被撤回的学术论文。

AI 生成摘要 · Google Gemini · 来自 1 个来源。我们如何撰写摘要 →

报道来源 [1]

arXiv cs.LG TIER_1 English(EN) · Micha{\l} Szyfelbein · 2026-04-29 04:00

Uniform Decision Tree 的常数因子近似

arXiv:2604.12036v2 Announce Type: replace-cross 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 a…