Nous proposons deux algorithmes de type streaming en un seul passage pour le problème NP-difficile de couplage dans les hypergraphes. Le premier algorithme stocke un petit sous-ensemble d’arêtes candidates au couplage dans une pile, en utilisant des variables duales pour sélectionner les arêtes. Il garantit une approximation de $\frac{1}{d(1+\varepsilon)}$ et requiert $O((n/\varepsilon) \log^2{n})$ bits de mémoire, où $n$ est le nombre de sommets dans l'hypergraphe, $d$ est le nombre maximal de sommets dans une hyperarête, et $\epsilon > 0$ est un paramètre à choisir.Le second algorithme calcule, stocke et met à jour un unique couplage au fil du flux d’arêtes, avec un ratio d’approximation dépendant d’un paramètre $\alpha$. Son meilleur ratio d’approximation est $\frac{1}{(2d-1) + 2 \sqrt{d(d-1)}}$ et il ne nécessite que $O(n)$ de mémoire.Nous avons implémenté ces deux algorithmes et conçu des variantes visant à optimiser les poids du couplage, la consommation mémoire et le temps d’exécution. Celles-ci incluent des assouplissements des règles d’admission des arêtes dans la pile ainsi qu’un second passage pour améliorer le poids. L’évaluation a été réalisée sur de grands hypergraphes issus de la conception de circuits et du calcul de matrices creuses. Nos résultats montrent que les algorithmes de streaming atteignent en pratique des facteurs d’approximation bien meilleurs que les bornes dans le pire cas, réduisant la mémoire requise jusqu’à 50fois et surpassant l’algorithme glouton hors ligne.

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 $\epsilon > 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 $\alpha$. 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.