On the complexity of approximating k-set packing

Given a k-uniform hypergraph, the Maximumk -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 ext...

Full description

Saved in:
Bibliographic Details
Published in:Computational complexity 2006-05, Vol.15 (1), p.20-39
Main Authors: Hazan, Elad, Safra, Shmuel, Schwartz, Oded
Format: Article
Language:English
Subjects:
Approximation
Computer science
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a k-uniform hypergraph, the Maximumk -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.
ISSN:1016-3328
1420-8954
DOI:10.1007/s00037-006-0205-6