Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913234378817536 |
|---|---|
| author | Gil, Yuval |
| author_facet | Gil, Yuval |
| contents | We design new deterministic CONGEST approximation algorithms for \emph{maximum weight independent set (MWIS)} in \emph{sparse graphs}. As our main results, we obtain new $Δ(1+ε)$-approximation algorithms as well as algorithms whose approximation ratio depend strictly on $α$, in graphs with maximum degree $Δ$ and arboricity $α$. For (deterministic) $Δ(1+ε)$-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al.\ [SODA 2023] that showed an $O(\log^{2} (ΔW)\cdot \log (1/ε)+\log ^{*}n)$-round algorithm, where $W$ is the largest node-weight (this bound translates to $O(\log^{2} n\cdot\log (1/ε))$ under the common assumption that $W=\text{poly}(n)$). As for $α$-dependent approximations, a deterministic CONGEST $(8(1+ε)\cdotα)$-approximation algorithm with runtime $O(\log^{3} n\cdot\log (1/ε))$ can be derived by combining the aforementioned algorithm of Faour et al.\ with a method presented by Kawarabayashi et al.\ [DISC 2020]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_09011 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs Gil, Yuval Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We design new deterministic CONGEST approximation algorithms for \emph{maximum weight independent set (MWIS)} in \emph{sparse graphs}. As our main results, we obtain new $Δ(1+ε)$-approximation algorithms as well as algorithms whose approximation ratio depend strictly on $α$, in graphs with maximum degree $Δ$ and arboricity $α$. For (deterministic) $Δ(1+ε)$-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al.\ [SODA 2023] that showed an $O(\log^{2} (ΔW)\cdot \log (1/ε)+\log ^{*}n)$-round algorithm, where $W$ is the largest node-weight (this bound translates to $O(\log^{2} n\cdot\log (1/ε))$ under the common assumption that $W=\text{poly}(n)$). As for $α$-dependent approximations, a deterministic CONGEST $(8(1+ε)\cdotα)$-approximation algorithm with runtime $O(\log^{3} n\cdot\log (1/ε))$ can be derived by combining the aforementioned algorithm of Faour et al.\ with a method presented by Kawarabayashi et al.\ [DISC 2020]. |
| title | Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2402.09011 |