期刊
COMPUTATIONAL COMPLEXITY
卷 15, 期 1, 页码 20-39出版社
SPRINGER BASEL AG
DOI: 10.1007/s00037-006-0205-6
关键词
computational complexity; hardness of approximation; set packing
Gi ven a k-uniform hypergraph, the MAXIMUM - Set PACKING problem is to find them maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of Omega ( k/In k) unless P = NP. This improves the previous hardness of approximation factor of k/ 2(O) (root In k) by Trevisan. This result extends to the problem of k-Dimensional-Matching.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据