Passing the Limits of Pure Local Search for Weighted k-Set Packing

We study the weighted k-Set Packing problem, which is defined as follows: Given a collection S of sets, each of cardinality at most k, together with a positive weight function w : S → Q >0 , the task is to compute a sub-collection A ⊆ S of maximum total weight such that the sets in A are pairwise disjoint. For k ≤ 2, the weighted k-Set Packing problem reduces to the Maximum Weight Matching problem, and can thus be solved in polynomial time [5]. However, for k ≥ 3, already the special case of unit weights, the unweighted k-Set Packing problem, becomes N P -hard as it generalizes the 3D-matching problem [8]. The state-of-the-art algorithms for both the unweighted and the weighted k-Set Packing problem rely on local search. In the unweighted setting, the best known approximation guarantee is k+1

3 + ǫ [6]. For general weights, Berman's algorithm SquareImp, which yields a k+1 2 + ǫ-approximation, has remained unchallenged for twenty years [1]. Only recently, Neuwohner managed to improve on this by obtaining approximation guarantees of k+ǫ k 2 with lim k→∞ ǫ k = 0 [10]. She further showed her result to be asymptotically best possible in that no algorithm considering local improvements of logarithmically bounded size with respect to some fixed power of the weight function can yield an approximation guarantee better than k 2 [10]. In this paper, we finally show how to beat the threshold of k 2 for the weighted k-Set Packing problem by Ω(k). We achieve this by combining local search with the application of a black box algorithm for the unweighted k-Set Packing problem to carefully chosen sub-instances. In doing so, we do not only manage to link the approximation ratio for general weights to the one achievable in the unweighted case. In contrast to previous works, which yield an improvement over Berman's long-standing result of k+1 2 + ǫ either only for large values of k ≥ 2 • 10 5 [10], or by less than 6 • 10 -7 [9], we achieve guarantees of at most k+1 2 -2 • 10 -4 for all k ≥ 4.