Asymptotically Optimal Hardness for \({k}\)-Set Packing and \({k}\)-Matroid Intersection

Abstract. For any [Formula: see text], we prove that [Formula: see text]-Dimensional Matching is hard to approximate within a factor of [Formula: see text] for large [Formula: see text] unless [Formula: see text]. Listed in Karp’s 21 [Formula: see text]-complete problems, [Formula: see text]-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: [Formula: see text]-Set Packing, [Formula: see text]-Matroid Intersection, and Matroid [Formula: see text]-Parity. For all the aforementioned problems, the best-known lower bound was a [Formula: see text]-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieve an approximation of [Formula: see text]. 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 [Formula: see text]-degree bounded [Formula: see text]-CSPs over alphabet size [Formula: see text] to [Formula: see text]-Dimensional Matching. Along the way, we prove that [Formula: see text]-degree bounded [Formula: see text]-CSPs over alphabet size [Formula: see text] are hard to approximate within a factor [Formula: see text] using known randomised sparsification methods for CSPs.