Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
Nikhil Bansal, David G. Harris · Random Structures and Algorithms · 2022
Abstract A classic conjecture of Füredi, Kahn, and Seymour (1993) states that any hypergraph with non‐negative edge weights has a matching such that , where is the value of an optimum fractional matching. We show the conjecture is true for rank‐3 hypergraphs and is achieved by a natural iterated rounding algorithm. While the general conjecture remains open, we give several new improved bounds. In particular, we show that the iterated rounding algorithm gives , where , improving upon the baseline guarantee of .