Prophet Secretary and Matching: the Significance of the Largest Item
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910681660391424 |
|---|---|
| author | Chen, Ziyun Huang, Zhiyi Li, Dongchen Tang, Zhihao Gavin |
| author_facet | Chen, Ziyun Huang, Zhiyi Li, Dongchen Tang, Zhihao Gavin |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01191 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Prophet Secretary and Matching: the Significance of the Largest Item Chen, Ziyun Huang, Zhiyi Li, Dongchen Tang, Zhihao Gavin Data Structures and Algorithms Computer Science and Game Theory 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). |
| title | Prophet Secretary and Matching: the Significance of the Largest Item |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2411.01191 |