Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929451817762816 |
|---|---|
| author | Pashkovich, Kanstantsin Sayutina, Alice |
| author_facet | Pashkovich, Kanstantsin Sayutina, Alice |
| contents | We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight $2$-competitive mechanism for all matroids.
However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this work, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_01700 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids Pashkovich, Kanstantsin Sayutina, Alice Computer Science and Game Theory We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight $2$-competitive mechanism for all matroids. However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this work, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms. |
| title | Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2301.01700 |