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