EUVIMEDEUVIMED entdecken
Crossref

Prophet Secretary and Matching: the Significance of the Largest Item

Ziyun Chen, Zhiyi Huang, Dongchen Li, Zhihao Gavin Tang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →