On the complexity of approximating k-set packing |
| |
| Authors: | Elad Hazan Shmuel Safra Oded Schwartz |
| |
| Affiliation: | (1) Computer Science Department, Princeton University, Princeton, NJ, 08540, U.S.A.;(2) School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel |
| |
| 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
unless P = NP. This improves the previous hardness of approximation factor of
by Trevisan. This result extends to the problem of k-Dimensional-Matching. |
| |
| Keywords: | Computational complexity hardness of approximation set packing |
| 本文献已被 SpringerLink 等数据库收录！ |
|
