Almost Tight Bounds for Online Hypergraph Matching

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\"ive greedy algorithm for this problem achieves a competitive ratio of 1k. 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) (k) and show that no online algorithm can have competitive ratio strictly better than 1+o (1) (k). Lastly, we give a 1-o (1) (k) competitive algorithm for the fractional edge-weighted version of the problem under a free disposal assumption.