Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
<|reference_start|>Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection: For any $\varepsilon > 0$, we prove that $k$-Dimensional Matching is hard to approximate within a factor of $k/(12 + \varepsilon)$ for large $k$ unless $\textsf{NP} \subseteq \textsf{BPP}$. Listed in Karp's 21 $\textsf{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 $\Omega(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 $\Omega_k(R)$ using known randomised sparsification methods for CSPs.<|reference_end|>
@article{lee2024asymptotically,
    title={Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid
  Intersection},
    author={Euiwoong Lee, Ola Svensson, Theophile Thiery},
    journal={arXiv preprint arXiv:2409.17831},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.17831},
    primaryClass={cs.CC cs.DS math.CO}
}