On the complexity of approximating k-Set Packing

Elad E. Hazan, Shmuel Safra, Oded Schwartz

Research output: Contribution to journalArticle

112 Scopus citations

Abstract

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
Volume15
Issue number1
DOIs
StatePublished - May 1 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Mathematics(all)
  • Computational Mathematics

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

  • Cite this