Abstract:
We study bounded degree graph problems, mainly the problem of k-Dimensional Matching \emph{(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 efficiently approximated to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$. This improves the previous factor of $\frac{k}{2^{O(\sqrt{\ln k}})} $ by Trevisan \cite{trevisan}. For low $k$ values we prove NP-hardness factors of $\frac{54}{53} - \varepsilon,\frac{30}{29} - \varepsilon$ and $\frac{23}{22} - \varepsilon$ 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.