NeFut Logo NeFut
EN 管理员登录

[算法理论] 线性 Matroid 的强秘书猜想成立

发布于:2026-11-09 22:00 最后更新:2026-11-12 00:51
#algorithm #optimization #Math

我们证明了在线 Matroid 秘书问题在线性 Matroid 上可以实现 $1/e$ 的保证:对任意固定的最优基底中的每个元素,算法选中的概率至少为 $1/e$。该结果同时适用于两种信息模型——事先已知完整的 Matroid,或在元素到达时在线给出其线性表示。已知 Matroid 的情形进一步推广到完全模可扩展 Matroid。我们还在更一般的模型下得到相同的 $1/e$ 保证,无论 Matroid 是否已知。

在 XOS Matroid Secretary 中,具有 XOS 估值的代理按均匀随机顺序到达,算法需为每个到达的代理分配一组互不相交且整体独立的元素。我们证明期望总价值至少为离线最优的 $1/e$。该模型包含 Group Matroid Secretary,其中元素被对手划分为若干组,组以随机顺序到达,算法在每组中选择子集。对该特殊情形,同样可以保证对固定最优基底的每个元素选中概率不少于 $1/e$。

点评:该工作首次在广义的线性 Matroid 上确认了强秘书猜想,为后续在更复杂 Matroid 类别上的研究提供了明确的基准。

原文链接: https://arxiv.org/abs/2609.20797

[h] 返回首页