Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection

Euiwoong Lee, Ola Svensson, Theophile Thiery

For any $\epsilon >0$, we prove that $k$-Dimensional Matching is hard to approximate within a factor of $k/(12+\epsilon )$ for large $k$ unless $\textsf{NP} \subseteq \text…