On the complexity of approximating k-dimensional matching

Elad Hazan; Shmuel Safra; Oded Schwartz

doi:10.1007/978-3-540-45198-3_8

On the complexity of approximating k-dimensional matching

Elad Hazan, Shmuel Safra, Oded Schwartz

Research output: Chapter in Book/Report/Conference proceeding › Chapter

41 Scopus citations

Abstract

We study the complexity of bounded variants of graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of O(k/ln k) unless P = NP. This improves the previous factor of k/₂O(√ln k) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of 54/53-ε, 30/29-ε and 23/22-ε for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of k-Set-Packing and the problem of Maximum Independent-Set in (k + 1)-claw-free graphs.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Sanjeev Asora, Amit Sahai, Klaus Jansen, Jose D.P. Rolim
Publisher	Springer Verlag
Pages	83-97
Number of pages	15
ISBN (Print)	3540407707, 9783540407706
DOIs	https://doi.org/10.1007/978-3-540-45198-3_8
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2764
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45198-3_8

Cite this

Hazan, E., Safra, S., & Schwartz, O. (2003). On the complexity of approximating k-dimensional matching. In S. Asora, A. Sahai, K. Jansen, & J. D. P. Rolim (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 83-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764). Springer Verlag. https://doi.org/10.1007/978-3-540-45198-3_8

Hazan, Elad ; Safra, Shmuel ; Schwartz, Oded. / On the complexity of approximating k-dimensional matching. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Sanjeev Asora ; Amit Sahai ; Klaus Jansen ; Jose D.P. Rolim. Springer Verlag, 2003. pp. 83-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{1af77d4706cd4dcd8f71436d8606a701,

title = "On the complexity of approximating k-dimensional matching",

abstract = "We study the complexity of bounded variants of graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of O(k/ln k) unless P = NP. This improves the previous factor of k/2O(√ln k) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of 54/53-ε, 30/29-ε and 23/22-ε for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of k-Set-Packing and the problem of Maximum Independent-Set in (k + 1)-claw-free graphs.",

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

year = "2003",

doi = "10.1007/978-3-540-45198-3_8",

language = "English (US)",

isbn = "3540407707",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "83--97",

editor = "Sanjeev Asora and Amit Sahai and Klaus Jansen and Rolim, {Jose D.P.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Hazan, E, Safra, S & Schwartz, O 2003, On the complexity of approximating k-dimensional matching. in S Asora, A Sahai, K Jansen & JDP Rolim (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2764, Springer Verlag, pp. 83-97. https://doi.org/10.1007/978-3-540-45198-3_8

On the complexity of approximating k-dimensional matching. / Hazan, Elad; Safra, Shmuel; Schwartz, Oded.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Sanjeev Asora; Amit Sahai; Klaus Jansen; Jose D.P. Rolim. Springer Verlag, 2003. p. 83-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - On the complexity of approximating k-dimensional matching

AU - Hazan, Elad

AU - Safra, Shmuel

AU - Schwartz, Oded

PY - 2003

Y1 - 2003

N2 - We study the complexity of bounded variants of graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of O(k/ln k) unless P = NP. This improves the previous factor of k/2O(√ln k) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of 54/53-ε, 30/29-ε and 23/22-ε for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of k-Set-Packing and the problem of Maximum Independent-Set in (k + 1)-claw-free graphs.

AB - We study the complexity of bounded variants of graph problems, mainly the problem of k-Dimensional Matching (k-DM), namely, the problem of finding a maximal matching in a k-partite k-uniform balanced hyper-graph. We prove that k-DM cannot be efficiently approximated to within a factor of O(k/ln k) unless P = NP. This improves the previous factor of k/2O(√ln k) by Trevisan [Tre01]. For low k values we prove NP-hardness factors of 54/53-ε, 30/29-ε and 23/22-ε for 4-DM, 5-DM and 6-DM respectively. These results extend to the problem of k-Set-Packing and the problem of Maximum Independent-Set in (k + 1)-claw-free graphs.

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

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

U2 - 10.1007/978-3-540-45198-3_8

DO - 10.1007/978-3-540-45198-3_8

M3 - Chapter

AN - SCOPUS:35248817378

SN - 3540407707

SN - 9783540407706

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 83

EP - 97

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Asora, Sanjeev

A2 - Sahai, Amit

A2 - Jansen, Klaus

A2 - Rolim, Jose D.P.

PB - Springer Verlag

ER -

Hazan E, Safra S, Schwartz O. On the complexity of approximating k-dimensional matching. In Asora S, Sahai A, Jansen K, Rolim JDP, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 83-97. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45198-3_8

On the complexity of approximating k-dimensional matching

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this