TR03-020 Authors: Elad Hazan, Shmuel Safra, Oded Schwartz

Publication: 3rd April 2003 19:44

Downloads: 3195

Keywords:

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.