On the Hardness of Approximating k-Dimensional Matching
Elad Hazan, Muli Safra, Oded Schwartz · 2003
We study bounded degree graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be e#ciently approximated to within a factor of O( ) unless P = NP . This improves the previous factor of 2 O( # ln k ) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of # for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of Maximum Independent-Set in (k + 1)-claw-free graphs and the problem of k-Set-Packing.