
























Abstract:In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.
| Subjects: | Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.22653 [cs.DS] |
| (or arXiv:2605.22653v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.22653 arXiv-issued DOI via DataCite (pending registration) |
From: Alexander Lindermayr [view email]
[v1]
Thu, 21 May 2026 15:56:09 UTC (806 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。