Towards an Optimal Contention Resolution Scheme for Matchings
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_ | 1866913482214998016 |
|---|---|
| author | Nuti, Pranav Vondrák, Jan |
| author_facet | Nuti, Pranav Vondrák, Jan |
| contents | In this paper, we study contention resolution schemes for matchings. Given a fractional matching $x$ and a random set $R(x)$ where each edge $e$ appears independently with probability $x_e$, we want to select a matching $M \subseteq R(x)$ such that $\Pr[e \in M \mid e \in R(x)] \geq c$, for $c$ as large as possible. We call such a selection method a $c$-balanced contention resolution scheme.
Our main results are (i) an asymptotically (in the limit as $\|x\|_\infty$ goes to 0) optimal $\simeq 0.544$-balanced contention resolution scheme for general matchings, and (ii) a $0.509$-balanced contention resolution scheme for bipartite matchings. To the best of our knowledge, this result establishes for the first time, in any natural relaxation of a combinatorial optimization problem, a separation between (i) offline and random order online contention resolution schemes, and (ii) monotone and non-monotone contention resolution schemes. We also present an application of our scheme to a combinatorial allocation problem, and discuss some open questions related to van der Waerden's conjecture for the permanent of doubly stochastic matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_03599 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Towards an Optimal Contention Resolution Scheme for Matchings Nuti, Pranav Vondrák, Jan Data Structures and Algorithms Discrete Mathematics Probability In this paper, we study contention resolution schemes for matchings. Given a fractional matching $x$ and a random set $R(x)$ where each edge $e$ appears independently with probability $x_e$, we want to select a matching $M \subseteq R(x)$ such that $\Pr[e \in M \mid e \in R(x)] \geq c$, for $c$ as large as possible. We call such a selection method a $c$-balanced contention resolution scheme. Our main results are (i) an asymptotically (in the limit as $\|x\|_\infty$ goes to 0) optimal $\simeq 0.544$-balanced contention resolution scheme for general matchings, and (ii) a $0.509$-balanced contention resolution scheme for bipartite matchings. To the best of our knowledge, this result establishes for the first time, in any natural relaxation of a combinatorial optimization problem, a separation between (i) offline and random order online contention resolution schemes, and (ii) monotone and non-monotone contention resolution schemes. We also present an application of our scheme to a combinatorial allocation problem, and discuss some open questions related to van der Waerden's conjecture for the permanent of doubly stochastic matrices. |
| title | Towards an Optimal Contention Resolution Scheme for Matchings |
| topic | Data Structures and Algorithms Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2211.03599 |