文章基本信息

标题：On the Hardness of Approximating k-Dimensional Matching
本地全文：下载
作者：Elad Hazan ; Shmuel Safra ; Oded Schwartz 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 ( k ln k ) unless P = N P . This improves the previous factor of k 2 O ( ln k ) by Trevisan \cite{trevisan}. For low k values we prove NP-hardness factors of 53 54 − 29 30 − and 22 23 − 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.
关键词：Approximation , degree , kdm , matching