Qing Li, Zhigang Deng, et al.
IEEE T-MI
We consider the classical matroid matching problem. Unweighted matroid matching for linearly represented matroids was solved by Lovász, and the problem is known to be intractable for general matroids. We present a polynomial-time approximation scheme for unweighted matroid matching for general matroids. In contrast, we show that natural linear-programming relaxations that have been studied have an Ω(n) integrality gap, and, moreover, Ω(n) rounds of the Sherali- Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed k ≥ 2 and ε > 0, we obtain a (k/2+ε)-approximation for matroid matching in k-uniform hypergraphs, also known as the matroid k-parity problem. As a consequence, we obtain a (k/2+ε)-approximation for the problem of finding the maximum-cardinality set in the intersection of k matroids. We also give a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem. © 2013 Society for Industrial and Applied Mathematics.