Improved Approximation Algorithms for Weighted <em>k</em>-Set Packing

Abstract

We study the weighted k-Set Packing problem, which is defined as follows: The input consists of a finite collection S of non-empty sets, each of cardinality at most k, as well as a positive weight for each of the sets. The task is to compute a subcollection A of S such that the sets in A are pairwise disjoint and the total weight of A is maximum. <br /> For k=1 and k=2, the weighted k-Set Packing problem can be solved in polynomial time. In contrast, if k is at least 3, even the special case where all weights are equal to 1, the unweighted k-Set Packing problem, is NP-hard. <br /> In this thesis, we study polynomial-time approximation algorithms for (variants of) the weighted k-Set Packing problem for k greater or equal to 3. The technique that has proven most successful in designing these algorithms is local search. <br /> The state-of-the-art algorithms for the unweighted case are due to Cygan and Fürer and Yu . They use well-structured local improvements of up to logarithmic size and attain approximation ratios of (k+1+epsilon)/3. For general weights, only local improvements of constant size have been studied prior to the results presented in this thesis. Berman has devised a (k+1+epsilon)/2-approximation algorithm. By considering a broader class of local improvements of constant size, I obtained an improved guarantee of (k+1+epsilon)/2-1/63,700,992 in the course of my Master's thesis. <br /> In this PhD thesis, we first show that a much smaller class of local improvements than in our previous work suffices to obtain an approximation ratio of (k+1)/2-1/1000. Next, we address the question which approximation guarantees can be achieved for the weighted k-Set Packing problem via local improvements of logarithmically bounded size, and provide an asymptotically tight answer. We obtain approximation guarantees of (k+1+lambda_k)/2, where lambda_k converges to 1 as k approaches infinity. Moreover, we establish a lower bound of k/2 By applying a black box algorithm for the unweighted k-Set Packing problem to generate candidate local improvements of potentially super-logarithmic size, we manage to breach the k/2 barrier and obtain approximation guarantees of 0.4999*k + 0.501 for the weighted k-Set Packing problem. We further leverage the above approach to establish a general link between approximation guarantees achievable for the unweighted and the weighted k-Set Packing problem. <br /> Finally, we provide a 4/3-approximation for the hereditary 2-3-Set Packing problem, a special case of weighted 3-Set Packing. Using a reduction by Fernandes and Lintzmayer, this further implies a 4/3-approximation for the Maximum Leaf Spanning Arborescence problem in acyclic digraphs. Our result improves upon the previously best known guarantee of 7/5 for both problems.