A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910705870962688 |
|---|---|
| author | Alon, Noga Gravin, Nick Pollner, Tristan Rubinstein, Aviad Wang, Hongao Weinberg, S. Matthew Zhang, Qianfan |
| author_facet | Alon, Noga Gravin, Nick Pollner, Tristan Rubinstein, Aviad Wang, Hongao Weinberg, S. Matthew Zhang, Qianfan |
| contents | We investigate prophet inequalities with competitive ratios approaching $1$, seeking to generalize $k$-uniform matroids. We first show that large girth does not suffice: for all $k$, there exists a matroid of girth $\geq k$ and a prophet inequality instance on that matroid whose optimal competitive ratio is $\frac{1}{2}$. Next, we show $k$-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio $1-O(\sqrt{\frac{\log k}{k}})$ for any $k$-fold matroid union. Our prophet inequality follows from an online contention resolution scheme.
The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone $1$-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a $1$-Lipschitz function that is not (approximately) self-bounding. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11741 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions Alon, Noga Gravin, Nick Pollner, Tristan Rubinstein, Aviad Wang, Hongao Weinberg, S. Matthew Zhang, Qianfan Data Structures and Algorithms Probability We investigate prophet inequalities with competitive ratios approaching $1$, seeking to generalize $k$-uniform matroids. We first show that large girth does not suffice: for all $k$, there exists a matroid of girth $\geq k$ and a prophet inequality instance on that matroid whose optimal competitive ratio is $\frac{1}{2}$. Next, we show $k$-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio $1-O(\sqrt{\frac{\log k}{k}})$ for any $k$-fold matroid union. Our prophet inequality follows from an online contention resolution scheme. The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone $1$-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a $1$-Lipschitz function that is not (approximately) self-bounding. |
| title | A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2411.11741 |