On the complexity of approximating k-Set Packing

Elad Hazan, Shmuel Safra, Oded Schwartz

Research output: Contribution to journalArticlepeer-review

141 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)20-39
Number of pages20
JournalComputational Complexity
Issue number1
StatePublished - May 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Computational complexity
  • Hardness of approximation
  • Set packing


Dive into the research topics of 'On the complexity of approximating k-Set Packing'. Together they form a unique fingerprint.

Cite this