Given a k-uniform hypergraph. the MAXIMUM k-SET PACKING problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of Ω(k/ln k) unless P = NP. This improves the previous hardness of approximation factor of k/2 O(√ln k) by Trevisan. This result extends to the problem of k-Dimensional-Matching.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Theory and Mathematics
- Computational Mathematics
- Computational complexity
- Hardness of approximation
- Set packing