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

State | Published - May 1 2006 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computational Theory and Mathematics
- Mathematics(all)
- Computational Mathematics

## Fingerprint Dive into the research topics of 'On the complexity of approximating k-Set Packing'. Together they form a unique fingerprint.

## Cite this

Hazan, E. E., Safra, S., & Schwartz, O. (2006). On the complexity of approximating k-Set Packing.

*Computational Complexity*,*15*(1), 20-39. https://doi.org/10.1007/s00037-006-0205-6