matroid | BriefGPT - AI 论文速递

关键词matroid

搜索结果 - 7

通过快速不精确的预言加速拟阵优化
复杂模型的查询通常需要复杂的计算和长时间的响应，因此弱模型能够快速提供不准确的结果，在使用少量查询到更强大的模型解决不准确性时具有优势。本文设计和分析了实用的算法，仅使用少量准确查询来处理低质量的不准确模型，接近于给定问题的经典算法性能，并
PDF5 months ago
基于拟阵的删除鲁棒子模型最大化
本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。
PDF2 years ago
关于张量分解的 Kruskal 定理的推广
该研究证明了一种名为 “分裂定理” 的数学定理，它可在张量分解的过程中降低 Kruskal 定理中的 k 秩条件并且使得该过程对于张量的唯一分解的要求更加宽松，从而实现了对于低于某个阈值的 k 秩的张量的唯一性的证明。
PDF3 years ago
对数凸多项式 II：高维随机游走和计算拟阵基数的 FPRAS
本篇论文设计了一种 FPRAS 来计算基于独立集先验的任何线性族的基数，估算处于 $0<q<1$ 区间的任何线性族的随机团模型的分区函数，并证明了任何线性族的基交换图具有至少 1 的扩张，并研究了纯单纯复合物和多项式的密切联系。
PDF6 years ago
基于矩阵约束的多臂赌博纯探索
研究了在随机多臂赌博游戏中受拟阵约束（Best-Basis）的纯勘探问题，提供了几乎最优样本复杂度的算法，以确定拟阵的基并达到最大总权重。
PDF8 years ago
Matroid Bandits: 快速组合优化与学习
通过结合 bandit 和 matroid 的思想，本篇论文提出了一种新型组合赌博算法 ——matroid bandits，它的目标是在 matroid 中最大化一个随机的初始未知的模块化函数，并提供了一种切实可行的算法 —— 乐观 mat
PDF10 years ago
信息有限条件下的预言不等式
研究 Prophet 不等式的单一样本算法及其应用，提出了一个基于随机游走的算法，用于选择任意 k 个项目或独立集。提供一种将特定类型的解决方案转换为单样本 Prophet 不等式的黑匣子方法，并在对称出价者的有限信息设置中设计了第一个公告
PDF11 years ago