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.