2024/02/13 by Thorben Tröbst, Tröbst, Thorben, Rajan Udwani +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Optimization and Search Problems #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2402.08775
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.