2026-07-23T20:44:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24547 2025-12-16T14:00:39Z ddc:004 open_access

Semi-Streaming Algorithms for Hypergraph Matching Reinstädtler, Henrik Ferdous, S M Pothen, Alex Uçar, Bora Schulz, Christian hypergraph matching semi-streaming We propose two one-pass streaming algorithms for the 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 1/(d(1+ε)) and requires 𝒪((n/ε)log²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 1/((2d-1) + 2 √{d(d-1)}), and it requires only 𝒪(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henrik Reinstädtler and S M Ferdous and Alex Pothen and Bora Uçar and Christian Schulz 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.79 urn:nbn:de:0030-drops-245478 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.79 eng https://creativecommons.org/licenses/by/4.0/legalcode