Semi-Streaming Algorithms for Hypergraph Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916830755422208 |
|---|---|
| author | Reinstädtler, Henrik Ferdous, S M Pothen, Alex Uçar, Bora Schulz, Christian |
| author_facet | Reinstädtler, Henrik Ferdous, S M Pothen, Alex Uçar, Bora Schulz, Christian |
| contents | We propose two one-pass streaming algorithms for the $\mathcal{NP}$-hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a stack using dual variables to select edges. It has an approximation guarantee of $\frac{1}{d(1+\varepsilon)}$ and requires $\mathcal{O}((\frac{n}{\varepsilon}) \log^2{n})$ bits of memory, where $n$ is the number of vertices in the hypergraph, $d$ is the maximum number of vertices in a hyperedge, and $ε> 0$ is a parameter to be chosen. The second algorithm computes, stores, and updates a single matching as the edges stream, with an approximation ratio dependent on a parameter $α$. Its best approximation guarantee is $\frac{1}{(2d-1) + 2 \sqrt{d(d-1)}}$, and it requires only $\mathcal{O}(n)$ memory.
We have implemented both algorithms and compared them with respect to solution quality, memory consumption, and running times on two diverse sets of hypergraphs with a non-streaming greedy and a naive streaming algorithm. Our results show that the streaming algorithms achieve much better solution quality than naive algorithms when facing adverse orderings. Furthermore, these algorithms reduce the memory required by a factor of 13 in the geometric mean on our test problems, and also outperform the offline Greedy algorithm in running time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13636 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semi-Streaming Algorithms for Hypergraph Matching Reinstädtler, Henrik Ferdous, S M Pothen, Alex Uçar, Bora Schulz, Christian Data Structures and Algorithms We propose two one-pass streaming algorithms for the $\mathcal{NP}$-hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a stack using dual variables to select edges. It has an approximation guarantee of $\frac{1}{d(1+\varepsilon)}$ and requires $\mathcal{O}((\frac{n}{\varepsilon}) \log^2{n})$ bits of memory, where $n$ is the number of vertices in the hypergraph, $d$ is the maximum number of vertices in a hyperedge, and $ε> 0$ is a parameter to be chosen. The second algorithm computes, stores, and updates a single matching as the edges stream, with an approximation ratio dependent on a parameter $α$. Its best approximation guarantee is $\frac{1}{(2d-1) + 2 \sqrt{d(d-1)}}$, and it requires only $\mathcal{O}(n)$ memory. We have implemented both algorithms and compared them with respect to solution quality, memory consumption, and running times on two diverse sets of hypergraphs with a non-streaming greedy and a naive streaming algorithm. Our results show that the streaming algorithms achieve much better solution quality than naive algorithms when facing adverse orderings. Furthermore, these algorithms reduce the memory required by a factor of 13 in the geometric mean on our test problems, and also outperform the offline Greedy algorithm in running time. |
| title | Semi-Streaming Algorithms for Hypergraph Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.13636 |