Almost tight bounds for online hypergraph matching
Thorben Tröbst, Rajan Udwani · Operations Research Letters · 2024
In the online hypergraph matching problem, hyperedges of size k over a common ground set arrive online in adversarial order. The goal is to obtain a maximum matching (disjoint set of hyperedges). A naïve greedy algorithm for this problem achieves a competitive ratio of 1 k . We show that no (randomized) online algorithm has competitive ratio better than 2 + o ( 1 ) k . If edges are allowed to be assigned fractionally, we give a deterministic online algorithm with competitive ratio 1 − o ( 1 ) ln ( k ) and show that no online algorithm can have competitive ratio strictly better than 1 + o ( 1 ) ln ( k ) . Lastly, we give a 1 − o ( 1 ) ln ( k ) competitive algorithm for the fractional edge-weighted version of the problem under a free disposal assumption.