On the Correlation Gap of Matroids
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917699843522560 |
|---|---|
| author | Husić, Edin Koh, Zhuan Khye Loho, Georg Végh, László A. |
| author_facet | Husić, Edin Koh, Zhuan Khye Loho, Georg Végh, László A. |
| contents | A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is at least $1-1/e$, and this is tight for simple matroid rank functions.
We initiate a fine-grained study of the correlation gap of matroid rank functions. In particular, we present an improved lower bound on the correlation gap as parametrized by the rank and girth of the matroid. We also show that for any matroid, the correlation gap of its weighted matroid rank function is minimized under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_09896 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Correlation Gap of Matroids Husić, Edin Koh, Zhuan Khye Loho, Georg Végh, László A. Optimization and Control Data Structures and Algorithms Computer Science and Game Theory A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is at least $1-1/e$, and this is tight for simple matroid rank functions. We initiate a fine-grained study of the correlation gap of matroid rank functions. In particular, we present an improved lower bound on the correlation gap as parametrized by the rank and girth of the matroid. We also show that for any matroid, the correlation gap of its weighted matroid rank function is minimized under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. |
| title | On the Correlation Gap of Matroids |
| topic | Optimization and Control Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2209.09896 |