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

Abstract

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 $\text{NP}\subseteq \text{BPP}$. Listed in Karp's 21 $\text{NP}$-complete problems, $k$-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: $k$-Set Packing, $k$-Matroid Intersection, and Matroid $k$-Parity. For all the aforementioned problems, the best known lower bound was a $\hat{I}\text{c◯}(k/\log (k))$-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieved an approximation of $O(k)$. Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. The crux of our result hinges on a novel approximation preserving gadget from $R$-degree bounded $k$-CSPs over alphabet size $R$ to $kR$-Dimensional Matching. Along the way, we prove that $R$-degree bounded $k$-CSPs over alphabet size $R$ are hard to approximate within a factor $\hat{I}{\text{c◯}}_k(R)$ using known randomised sparsification methods for CSPs.

14 pages