Weighted Matching in the Random-Order Streaming and Robust Communication Models
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913483313905664 |
|---|---|
| author | Hashemi, Diba Wrzos-Kaminska, Weronika |
| author_facet | Hashemi, Diba Wrzos-Kaminska, Weronika |
| contents | We study the maximum weight matching problem in the random-order semi-streaming model and in the robust communication model. Unlike many other sublinear models, in these two frameworks, there is a large gap between the guarantees of the best known algorithms for the unweighted and weighted versions of the problem.
In the random-order semi-streaming setting, the edges of an $n$-vertex graph arrive in a stream in a random order. The goal is to compute an approximate maximum weight matching with a single pass over the stream using $O(n\text{ polylog } n)$ space. Our main result is a $(2/3-ε)$-approximation algorithm for maximum weight matching in random-order streams, using space $O(n \log n \log R)$, where $R$ is the ratio between the heaviest and the lightest edge in the graph. Our result nearly matches the best known unweighted $(2/3+ε_0)$-approximation (where $ε_0 \sim 10^{-14}$ is a small constant) achieved by Assadi and Behnezhad [ICALP 2021], and significantly improves upon previous weighted results.
Our techniques also extend to the related robust communication model, in which the edges of a graph are partitioned randomly between Alice and Bob. Alice sends a single message of size $O(n\text{ polylog }n)$ to Bob, who must compute an approximate maximum weight matching. We achieve a $(5/6-ε)$-approximation using $O(n \log n \log R)$ words of communication, matching the results of Azarmehr and Behnezhad [ICALP 2023] for unweighted graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15434 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Weighted Matching in the Random-Order Streaming and Robust Communication Models Hashemi, Diba Wrzos-Kaminska, Weronika Data Structures and Algorithms We study the maximum weight matching problem in the random-order semi-streaming model and in the robust communication model. Unlike many other sublinear models, in these two frameworks, there is a large gap between the guarantees of the best known algorithms for the unweighted and weighted versions of the problem. In the random-order semi-streaming setting, the edges of an $n$-vertex graph arrive in a stream in a random order. The goal is to compute an approximate maximum weight matching with a single pass over the stream using $O(n\text{ polylog } n)$ space. Our main result is a $(2/3-ε)$-approximation algorithm for maximum weight matching in random-order streams, using space $O(n \log n \log R)$, where $R$ is the ratio between the heaviest and the lightest edge in the graph. Our result nearly matches the best known unweighted $(2/3+ε_0)$-approximation (where $ε_0 \sim 10^{-14}$ is a small constant) achieved by Assadi and Behnezhad [ICALP 2021], and significantly improves upon previous weighted results. Our techniques also extend to the related robust communication model, in which the edges of a graph are partitioned randomly between Alice and Bob. Alice sends a single message of size $O(n\text{ polylog }n)$ to Bob, who must compute an approximate maximum weight matching. We achieve a $(5/6-ε)$-approximation using $O(n \log n \log R)$ words of communication, matching the results of Azarmehr and Behnezhad [ICALP 2023] for unweighted graphs. |
| title | Weighted Matching in the Random-Order Streaming and Robust Communication Models |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.15434 |