Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture

Abstract

A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-uniform hypergraph matching states that for any hypergraph with edge weights $w$, there exists a matching $M$ such that the inequality ${\sum }_{e\in M}g(e)w(e)\ge {\mathrm{OPT}}_{\mathrm{LP}}$ holds with $g(e)=|e|-1+\frac{1}{|e|}$, where ${\mathrm{OPT}}_{\mathrm{LP}}$ denotes the optimal value of the canonical LP relaxation. While the conjecture remains open, the strongest result towards it was very recently obtained by Brubach, Sankararaman, Srinivasan, and Xu (2020)---building on and strengthening prior work by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (2012)---showing that the aforementioned inequality holds with $g(e)=|e|+O(|e|\exp (-|e|))$. Actually, their method works in a more general sampling setting, where, given a point $x$ of the canonical LP relaxation, the task is to efficiently sample a matching $M$ containing each edge $e$ with probability at least $\frac{x(e)}{g(e)}$. We present simpler and easy-to-analyze procedures leading to improved results. More precisely, for any solution $x$ to the canonical LP, we introduce a simple algorithm based on exponential clocks for Brubach et al.'s sampling setting achieving $g(e)=|e|-(|e|-1)x(e)$. Apart from the slight improvement in $g$, our technique may open up new ways to attack the original conjecture. Moreover, we provide a short and arguably elegant analysis showing that a natural greedy approach for the original setting of the conjecture shows the inequality for the same $g(e)=|e|-(|e|-1)x(e)$ even for the more general hypergraph $b$-matching problem.

Reorganized the appendix