带预测的多选秘书问题：更精细分析移除对数因子
Multiple-Choice Secretary Problem with Predictions
AI 导读
Shaojie Tang 通过对 Fujii 和 Yoshida 的 Learned Kleinberg 切换算法更精细的分析并重新调整阈值，改进了带预测的多选 secretary 问题竞争比，去掉了 O(min{log k/√k, ε}) 中的对数因子。新竞争比至少为 max{0, 1 − min{32/√k, 4ε}}；当预测完全准确（ε=0）时，无论候选人到达顺序如何都能达到离线最优。
正文 · 原文
Abstract:We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most $k$ candidates to maximize their total value. We consider a setting where predictions of individual candidate values are available before any candidate arrives. Fujii and Yoshida's Learned Kleinberg algorithm achieves competitive loss $O(\min\{\log k/\sqrt{k},\eps\})$, where $k$ is the selection capacity and $\eps$ is the maximum multiplicative prediction error. We remove the logarithmic factor through a sharper analysis of the same switching algorithm with a retuned threshold. The resulting competitive ratio is at least $\max\{0,1-\min\{32/\sqrt{k},4\eps\}\}$. In particular, exact predictions ($\eps=0$) achieve the offline optimum on every arrival order.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.14651 [cs.DS] |
| (or arXiv:2611.14651v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2611.14651 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shaojie Tang [view email]
[v1]
Tue, 10 Nov 2026 19:02:44 UTC (31 KB)
来源：arXiv cs.AI · arxiv.org