Matroid matching: the power of local search
Matroid matching: the power of local search
复制标题
拟阵匹配：本地搜索的力量
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Jon Lee;M. Sviridenko;J. Vondrák
我们考虑了洛夫斯（Lovasz）的经典矩阵匹配问题。 LP松弛具有ω（n）完整性差距，此外，Sherali-Adams层次结构的ω（n）回合是将差距降低到常数的必要条件。对于任何固定的k> = 2和ε> 0，我们获得了在k-均匀的超图中的矩阵匹配的A（K/2+ε） - 也称为Matroid K-Parity问题。 （K/2+ε） - 在K Matroids中找到最大信号的问题，我们还为Matroid匹配的特殊情况设计了3/2- approximation问题。
We consider the classical matroid matching problem. Unweighted matroid matching for linear matroids was solved by Lovasz, and the problem is known to be intractable for general matroids. We present a PTAS for unweighted matroid matching for general matroids. In contrast, we show that natural LP relaxations 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 have also designed a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem.