zbMATH — the first resource for mathematics

On the complexity of approximating \(k\)-set packing. (English) Zbl 1103.90105
Summary: 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 \(\Omega {({k/\ln k})}\) unless \(\text{P} = \text{NP}\). This improves the previous hardness of approximation factor of \(k/2^{{O({\sqrt {\ln k}})}}\) by Trevisan. This result extends to the problem of \(k\)-Dimensional-Matching.

90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX Cite
Full Text: DOI