Journal
COMPUTATIONAL COMPLEXITY
Volume 15, Issue 1, Pages 20-39Publisher
SPRINGER BASEL AG
DOI: 10.1007/s00037-006-0205-6
Keywords
computational complexity; hardness of approximation; set packing
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available