arXiv · cs.AI 人工智能· Jing Yuan, Qi Cai, Xin Gao, Shaojie Tang·· 5 小时前AI 评分40
多选秘书问题与预测:去除 Learned Kleinberg 算法的对数因子
Multiple-Choice Secretary Problem with Predictions
AI 导读
针对带预测的多选秘书问题,该研究改进了 Fujii 与 Yoshida 的 Learned Kleinberg 算法,通过更精细的分析与重新调整的阈值去掉了竞争损失中的对数因子,竞争比至少为 max{0,1-min{32/√k,4ε}}。当预测精确(ε=0)时,该算法在任意到达顺序下都能达到离线最优。
来源:arXiv · cs.AI 人工智能 · arxiv.org