Asymptotically Optimal Hardness for π-Set Packing and π-Matroid Intersection
Euiwoong Lee, Ola Svensson, Theophile Thiery Β· 2025
For any π > 0, we prove that π-Dimensional Matching is hard to approximate within a factor of π/(12+π) for large π unless NP β BPP. Listed in Karpβs 21 NP-complete problems, π-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: π-Set Packing, π-Matroid Intersection, and Matroid π-Parity. For all the aforementioned problems, the best-known lower bound was a Ξ©(π/log(π))-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieve an approximation of π(π). 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 π -degree bounded π-CSPs over alphabet size π to ππ -Dimensional Matching. Along the way, we prove that π -degree bounded π-CSPs over alphabet size π are hard to approximate within a factor Ξ©π (π ) using known randomised sparsification methods for CSPs.