The Competition Complexity of Prophet Secretary
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916485537988608 |
|---|---|
| author | Ezra, Tomer Garbuz, Tamar |
| author_facet | Ezra, Tomer Garbuz, Tamar |
| contents | We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-ε)$-competition complexity for different classes of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1 - ε)$-approximation to the expected offline optimum on the original instance (without added copies).
We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the $(1-ε)$-competition complexity is $Θ(\ln(\frac{1}ε))$ (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal $(1-ε)$-competition complexity of $Θ\left(\frac{\ln(\frac{1}ε)}{\ln\ln(\frac{1}ε)}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-ε)$-competition complexity of general adaptive algorithms is $Θ(\sqrt{\ln(\frac{1}ε)})$, which is in sharp contrast to $Θ(\ln\ln(\frac{1}ε))$ in the i.i.d. case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10892 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Competition Complexity of Prophet Secretary Ezra, Tomer Garbuz, Tamar Computer Science and Game Theory We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-ε)$-competition complexity for different classes of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1 - ε)$-approximation to the expected offline optimum on the original instance (without added copies). We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the $(1-ε)$-competition complexity is $Θ(\ln(\frac{1}ε))$ (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal $(1-ε)$-competition complexity of $Θ\left(\frac{\ln(\frac{1}ε)}{\ln\ln(\frac{1}ε)}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-ε)$-competition complexity of general adaptive algorithms is $Θ(\sqrt{\ln(\frac{1}ε)})$, which is in sharp contrast to $Θ(\ln\ln(\frac{1}ε))$ in the i.i.d. case. |
| title | The Competition Complexity of Prophet Secretary |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2411.10892 |