Beating Two-Thirds For Random-Order Streaming Matching
We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and outpu...
Kaydedildi:
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Makale |
| Baskı/Yayın Bilgisi: |
2021
|
| Konular: | |
| Online Erişim: | https://arxiv.org/abs/2102.07011 http://arxiv.org/abs/2102.07011 |
| Etiketler: |
Etiket eklenmemiş, İlk siz ekleyin!
|
| _version_ | 1879172814960852992 |
|---|---|
| author | Assadi, Sepehr Behnezhad, Soheil |
| author_browse | Assadi, Sepehr Behnezhad, Soheil |
| author_facet | Assadi, Sepehr Behnezhad, Soheil |
| author_sort | Assadi, Sepehr |
| building | arXiv |
| collection | Acceso abierto |
| description | We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and output a large matching of $G$.
We prove that for an absolute constant $ε_0 > 0$, one can find a $(2/3 + ε_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3 + Ω(1))$-approximation is achievable. |
| first_indexed | 2026-10-15T23:47:22Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2102.07011</identifier><datestamp>2021-03-02</datestamp>
<dc:title>Beating Two-Thirds For Random-Order Streaming Matching</dc:title>
<dc:creator>Assadi, Sepehr</dc:creator>
<dc:creator>Behnezhad, Soheil</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and output a large matching of $G$.
We prove that for an absolute constant $ε_0 > 0$, one can find a $(2/3 + ε_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3 + Ω(1))$-approximation is achievable. </dc:description>
<dc:date>2021-02-13</dc:date>
<dc:date>2021-02-28</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2102.07011</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2102.07011</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2102.07011 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:47:22Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2102.070112021-03-02 Beating Two-Thirds For Random-Order Streaming Matching Assadi, Sepehr Behnezhad, Soheil Data Structures and Algorithms We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and output a large matching of $G$. We prove that for an absolute constant $ε_0 > 0$, one can find a $(2/3 + ε_0)$-approximate maximum matching of $G$ using $O(n \log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3 + Ω(1))$-approximation is achievable. 2021-02-13 2021-02-28 text https://arxiv.org/abs/2102.07011 http://arxiv.org/abs/2102.07011 |
| spellingShingle | Data Structures and Algorithms Assadi, Sepehr Behnezhad, Soheil Beating Two-Thirds For Random-Order Streaming Matching |
| title | Beating Two-Thirds For Random-Order Streaming Matching |
| title_full | Beating Two-Thirds For Random-Order Streaming Matching |
| title_fullStr | Beating Two-Thirds For Random-Order Streaming Matching |
| title_full_unstemmed | Beating Two-Thirds For Random-Order Streaming Matching |
| title_short | Beating Two-Thirds For Random-Order Streaming Matching |
| title_sort | beating two thirds for random order streaming matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2102.07011 http://arxiv.org/abs/2102.07011 |
| work_keys_str_mv | AT assadisepehr beatingtwothirdsforrandomorderstreamingmatching AT behnezhadsoheil beatingtwothirdsforrandomorderstreamingmatching |