← 研踪 PaperTrailarXiv:2611.14651 · v1
Multiple-Choice Secretary Problem with Predictions
首次提交 2026-11-11 03:02
版本更新 2026-11-11 03:02
雷达观测 2026-11-13 10:09
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 03:02 · 最新观测版本
Multiple-Choice Secretary Problem with Predictions
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.
查看此版本解读 →查看此版本原文 ↗