On Linear Programming Relaxations of Hypergraph Matching

is no good approximation algorithm for the problem in its most general form. We study the restricted case where every hyperedge consists of k vertices, known as k-Set Packing.

We show that the integrality gap (the maximum ratio of the fractional solution to the integral solution over all hypergraphs) is k-1+1/k, and that the integrality gap analysis is tight in general. The proof is by showing a fractional colouring with a small number of colours. The colouring is done in a greedy manner with the help of a good ordering of hyperedges, which is derived from the LP solution.

As a special case, we prove that by adding a Fano plane constraint which deals with a set of intersecting hyperedges, the integrality gap of the LP for unweighted 3-Set Packing can be improved from 7/3 to 2. The result is by detailed analysis on the structure of a counterexample H, where we show that there is no Fano plane in H and by a result of Furedi [F81], we conclude that the integrality gap is 2.

When the vertex set is partitioned into k sets so that each hyperedge contains one vertex from each set, we have the k-Dimensional Matching problem. In this case we show that the standard LP relaxation has an integrality gap of k-1. We remark that integrality gap analysis had been made by Furedi, Kahn and
Seymour [FKS93] in a more general form using a different approach, but their analysis does not directly yield an approximation algorithm. We obtain a (k-1)-approximation algorithm by combining the good ordering on thehyperedges with an algorithmic framework called local-ratio. This improves the previous
result for 3-Dimensional Matching from 2+\epsilon to 2.