Large graph limits of local matching algorithms on Configuration model graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918143890292736 |
|---|---|
| author | Aoudi, Mohamed Habib Aliou Diallo Moyal, Pascal Robin, Vincent |
| author_facet | Aoudi, Mohamed Habib Aliou Diallo Moyal, Pascal Robin, Vincent |
| contents | In this work, we propose a large-graph limit estimate of the matching coverage for several matching algorithms, on general graphs generated by the configuration model. For a wide class of {\em local} matching algorithms, namely, algorithms that only use information on the immediate neighborhood of the explored nodes, we propose a joint construction of the graph by the configuration model, and of the resulting matching on the latter graph. This leads to a generalization in infinite dimension of the differential equation method of Wormald: We keep track of the matching algorithm over time by a measure-valued CTMC, for which we prove the convergence, to the large-graph limit, to a deterministic hydrodynamic limit, identified as the unique solution of a system of ODE's in the space of integer measures. Then, the asymptotic proportion of nodes covered by the matching appears as a simple function of that solution. We then make this solution explicit for three particular local algorithms: the classical {\sc greedy} algorithm, and then the {\sc uni-min} and {\sc uni-max} algorithms, two variants of the greedy algorithm that select, as neighbor of any explored node, its neighbor having the least (respectively largest) residual degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18059 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Large graph limits of local matching algorithms on Configuration model graphs Aoudi, Mohamed Habib Aliou Diallo Moyal, Pascal Robin, Vincent Probability 05C80, 60J25, 91B68 In this work, we propose a large-graph limit estimate of the matching coverage for several matching algorithms, on general graphs generated by the configuration model. For a wide class of {\em local} matching algorithms, namely, algorithms that only use information on the immediate neighborhood of the explored nodes, we propose a joint construction of the graph by the configuration model, and of the resulting matching on the latter graph. This leads to a generalization in infinite dimension of the differential equation method of Wormald: We keep track of the matching algorithm over time by a measure-valued CTMC, for which we prove the convergence, to the large-graph limit, to a deterministic hydrodynamic limit, identified as the unique solution of a system of ODE's in the space of integer measures. Then, the asymptotic proportion of nodes covered by the matching appears as a simple function of that solution. We then make this solution explicit for three particular local algorithms: the classical {\sc greedy} algorithm, and then the {\sc uni-min} and {\sc uni-max} algorithms, two variants of the greedy algorithm that select, as neighbor of any explored node, its neighbor having the least (respectively largest) residual degree. |
| title | Large graph limits of local matching algorithms on Configuration model graphs |
| topic | Probability 05C80, 60J25, 91B68 |
| url | https://arxiv.org/abs/2410.18059 |