Semi-Streaming Algorithm

Semi-Streaming Algorithms
Semi-Streaming Algorithms for Hypergraph Matching

arXiv:2502.13636v1 Announce Type: new
Abstract: 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 $frac…