A short note about the learning-augmented secretary problem
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_ | 1866912101975457792 |
|---|---|
| author | Choo, Davin Ling, Chun Kai |
| author_facet | Choo, Davin Ling, Chun Kai |
| contents | We consider the secretary problem through the lens of learning-augmented algorithms. As it is known that the best possible expected competitive ratio is $1/e$ in the classic setting without predictions, a natural goal is to design algorithms that are 1-consistent and $1/e$-robust. Unfortunately, [FY24] provided hardness constructions showing that such a goal is not attainable when the candidates' true values are allowed to scale with $n$. Here, we provide a simple and explicit alternative hardness construction showing that such a goal is not achievable even when the candidates' true values are constants that do not scale with $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06583 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A short note about the learning-augmented secretary problem Choo, Davin Ling, Chun Kai Data Structures and Algorithms We consider the secretary problem through the lens of learning-augmented algorithms. As it is known that the best possible expected competitive ratio is $1/e$ in the classic setting without predictions, a natural goal is to design algorithms that are 1-consistent and $1/e$-robust. Unfortunately, [FY24] provided hardness constructions showing that such a goal is not attainable when the candidates' true values are allowed to scale with $n$. Here, we provide a simple and explicit alternative hardness construction showing that such a goal is not achievable even when the candidates' true values are constants that do not scale with $n$. |
| title | A short note about the learning-augmented secretary problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.06583 |