Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-020 | 27th March 2003 00:00

On the Hardness of Approximating k-Dimensional Matching

RSS-Feed




TR03-020
Authors: Elad Hazan, Shmuel Safra, Oded Schwartz
Publication: 3rd April 2003 19:44
Downloads: 3603
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