A framework for boosting matching approximation: parallel, distributed, and dynamic
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909738825940992 |
|---|---|
| author | Mitrović, Slobodan Sheu, Wen-Horng |
| author_facet | Mitrović, Slobodan Sheu, Wen-Horng |
| contents | This work designs a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter $ε> 0$ and an oracle access to a $Θ(1)$-approximate maximum matching algorithm $\mathcal{A}$. Then, by invoking $\mathcal{A}$ for $\text{poly}(1/ε)$ many times, the framework outputs a $1+ε$ approximation of a maximum matching. Our approach yields several improvements in terms of the number of invocations to $\mathcal{A}$:
(1) In MPC and CONGEST, our framework invokes $\mathcal{A}$ for $O(1/ε^7 \cdot \log(1/ε))$ times, substantially improving on $O(1/ε^{39})$ invocations following from [Fischer et al., STOC'22] and [Mitrovic et al., arXiv:2412.19057].
(2) In both online and offline fully dynamic settings, our framework yields an improvement in the dependence on $1/ε$ from exponential [Assadi et al., SODA25 and Liu, FOCS24] to polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01147 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A framework for boosting matching approximation: parallel, distributed, and dynamic Mitrović, Slobodan Sheu, Wen-Horng Data Structures and Algorithms This work designs a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter $ε> 0$ and an oracle access to a $Θ(1)$-approximate maximum matching algorithm $\mathcal{A}$. Then, by invoking $\mathcal{A}$ for $\text{poly}(1/ε)$ many times, the framework outputs a $1+ε$ approximation of a maximum matching. Our approach yields several improvements in terms of the number of invocations to $\mathcal{A}$: (1) In MPC and CONGEST, our framework invokes $\mathcal{A}$ for $O(1/ε^7 \cdot \log(1/ε))$ times, substantially improving on $O(1/ε^{39})$ invocations following from [Fischer et al., STOC'22] and [Mitrovic et al., arXiv:2412.19057]. (2) In both online and offline fully dynamic settings, our framework yields an improvement in the dependence on $1/ε$ from exponential [Assadi et al., SODA25 and Liu, FOCS24] to polynomial. |
| title | A framework for boosting matching approximation: parallel, distributed, and dynamic |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.01147 |