Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KDM:
Reports tagged with kdm:
TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

#### On the Hardness of Approximating k-Dimensional Matching

We study bounded degree graph problems, mainly the problem of
k-Dimensional Matching \emph{(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(\frac{k}{ \ln k})$ unless $P = NP$.
This ... more >>>

ISSN 1433-8092 | Imprint