Publication
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.