Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR03-020 | 27th March 2003 00:00

#### On the Hardness of Approximating k-Dimensional Matching

TR03-020
Authors: Elad Hazan, Shmuel Safra, Oded Schwartz
Publication: 3rd April 2003 19:44
Keywords:

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.

ISSN 1433-8092 | Imprint