Almost Tight Bounds for Online Hypergraph Matching
<|reference_start|>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 $\frac{1}{k}$. We show that no (randomized) online algorithm has competitive ratio better than $\frac{2+o(1)}{k}$. If edges are allowed to be assigned fractionally, we give a deterministic online algorithm with competitive ratio $\frac{1-o(1)}{\ln(k)}$ and show that no online algorithm can have competitive ratio strictly better than $\frac{1+o(1)}{\ln(k)}$. Lastly, we give a $\frac{1-o(1)}{\ln(k)}$ competitive algorithm for the fractional edge-weighted version of the problem under a free disposal assumption.<|reference_end|>
@article{tröbst2024almost,
    title={Almost Tight Bounds for Online Hypergraph Matching},
    author={Thorben Tr"obst, Rajan Udwani},
    journal={arXiv preprint arXiv:2402.08775},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08775},
    primaryClass={cs.DS}
}