On the complexity of approximating k-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.