arXiv ID:
2607.02150
arXiv 提交日期: 2026-07-02
基于贝尔曼证书的多秘书问题紧下界 / Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
1️⃣ 一句话总结
本文证明了在多个秘书招聘问题中,当候选人的能力值呈现有间隔的分布时,最优在线策略的遗憾(即与最优离线策略的收益差距)必须随问题规模呈对数平方增长,从而证实了此前上界研究的紧性,并引入了一种名为“贝尔曼证书”的新分析框架来系统化这类下界证明。