14 October 2022
Almost Tight Bounds for Online Hypergraph Matching
Thorben Trobst
Abstract: Consider the problem of matching hyperedges in a k-uniform hypergraph in an online fashion. The edges arrive one by one and must be matched immediately and irrevocably. For k = 2 it is known that the best achievable competitive ratio for both fractional and integral algorithms is 1/2 and a simple greedy algorithm achieves this ratio. We show that for k -> infinity, the best achievable competitive ratio in the fractional case is 1 / ln(k) and give an algorithm that achieves this. On the other hand, for the integral setting, we show that no algorithm can do better than 2/k asymptotically (again, a simple greedy algorithm gets 1/k). This yields a surprisingly large gap between the fractional and integral settings.
Joint work with Rajan Udwani