# 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.

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