Generalized Hypergraph Matching via Iterated Packing and Local Ratio

In \(k\)-hypergraph matching, we are given a collection of sets of size at most \(k\), each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwise disjoint. More generally, in \(k\)-hypergraph \(b\)-matching, instead of disjointness we require that every element appears in at most \(b\) sets of the subcollection. Our main result is a linear-programming based \((k-1+\tfrac{1}{k})\)-approximation algorithm for \(k\)-hypergraph \(b\)-matching. This settles the integrality gap when \(k\) is one more than a prime power, since it matches a previously-known lower bound. When the hypergraph is bipartite, we are able to improve the approximation ratio to \(k-1\), which is also best possible relative to the natural LP. These results are obtained using a more careful application of the iterated packing method.