Prophet Secretary and Matching: the Significance of the Largest Item
ACM Transactions on Algorithms · 05.05.2026
DOI: 10.1145/3811027 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 05.05.2026. Verfasst von Ziyun Chen und 3 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben.
Abstract (Originalsprache)
The prophet secretary problem is a combination of the prophet inequality and the secretary problem, where elements are drawn from known independent distributions and arrive in uniformly random order. In this work, we design 1) a \(0.688\) -competitive algorithm, that breaks the \(0.675\) barrier of blind strategies (Correa, Saona, Ziliotto, 2021), and 2) a \(0.641\) -competitive algorithm for the prophet secretary matching problem, that breaks the \(1-1/e\approx 0.632\) barrier for the first time. Our second result also applies to the query-commit model of weighted stochastic matching and improves the state-of-the-art ratio (Derakhshan and Farhadi, 2023).
Zitieren
APA
Chen, Z., Huang, Z., Li, D., & Tang, Z. G. (2026). Prophet Secretary and Matching: the Significance of the Largest Item. ACM Transactions on Algorithms. https://doi.org/10.1145/3811027
Vancouver
Chen Z, Huang Z, Li D, Tang ZG. Prophet Secretary and Matching: the Significance of the Largest Item. ACM Transactions on Algorithms. 2026. doi:10.1145/3811027
BibTeX
@article{Chen2026,
author = {Chen, Ziyun and Huang, Zhiyi and Li, Dongchen and Tang, Zhihao Gavin},
title = {Prophet Secretary and Matching: the Significance of the Largest Item},
journal = {ACM Transactions on Algorithms},
year = {2026},
doi = {10.1145/3811027}
}
EUVIMED