研究人员为拟阵算法引入了一种新的成本模型，该模型考虑了查询集的大小，超越了传统的常数时间假设。这种大小敏感的方法能更好地反映实际计算工作量，尤其对于图拟阵等自然拟阵类别。该研究为寻找基和近似秩等基本任务建立了严格的界限，表明最优查询成本通常是拟阵大小的二次方，但最大回路大小较小的拟阵除外。 AI
影响 为优化等领域的算法分析引入了更现实的理论模型，可能影响相关领域的未来研究。
排序理由 学术论文，介绍新的理论框架和算法结果。
AI 生成摘要 · Google Gemini · 来自 1 个来源。 我们如何撰写摘要 →
arXiv:2605.00201v1 Announce Type: cross Abstract: The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical prog…