On the complexity of approximating k-Set Packing

Elad Hazan; Shmuel Safra; Oded Schwartz

doi:10.1007/s00037-006-0205-6

On the complexity of approximating k-Set Packing

Elad Hazan, Shmuel Safra, Oded Schwartz

Research output: Contribution to journal › Article › peer-review

144 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 language	English (US)
Pages (from-to)	20-39
Number of pages	20
Journal	Computational Complexity
Volume	15
Issue number	1
DOIs	https://doi.org/10.1007/s00037-006-0205-6
State	Published - May 2006

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Keywords

Computational complexity
Hardness of approximation
Set packing

Access to Document

10.1007/s00037-006-0205-6

Cite this

@article{1403dac0f1524e8ebd85f7f33f1098b9,

title = "On the complexity of approximating k-Set Packing",

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.",

keywords = "Computational complexity, Hardness of approximation, Set packing",

author = "Elad Hazan and Shmuel Safra and Oded Schwartz",

year = "2006",

month = may,

doi = "10.1007/s00037-006-0205-6",

language = "English (US)",

volume = "15",

pages = "20--39",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "1",

}

TY - JOUR

T1 - On the complexity of approximating k-Set Packing

AU - Hazan, Elad

AU - Safra, Shmuel

AU - Schwartz, Oded

PY - 2006/5

Y1 - 2006/5

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

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

KW - Computational complexity

KW - Hardness of approximation

KW - Set packing

UR - http://www.scopus.com/inward/record.url?scp=33646508996&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646508996&partnerID=8YFLogxK

U2 - 10.1007/s00037-006-0205-6

DO - 10.1007/s00037-006-0205-6

M3 - Article

AN - SCOPUS:33646508996

SN - 1016-3328

VL - 15

SP - 20

EP - 39

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -

On the complexity of approximating k-Set Packing

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this