An Improved Approximation for Maximum Weighted <i>k</i>-Set Packing
Theophile Thiery, Justin Ward
Abstract
We consider the weighted k-set packing problem, in which we are given a collection of weighted sets, each with at most k elements and must return a collection of pairwise disjoint sets with maximum total weight. For k = 3, this problem generalizes the classical 3-dimensional matching problem listed as one of the Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of 1.786 for 3-set packing, improving on the recent best result of due to Neuwohner.
Topics & Concepts
Disjoint setsMathematicsApproximation algorithmCombinatoricsPacking problemsMatching (statistics)Pairwise comparisonSet (abstract data type)Independent setDiscrete mathematicsAlgorithmGraphMathematical optimizationComputer scienceStatisticsProgramming languageOptimization and Packing ProblemsAdvanced Graph Theory Researchgraph theory and CDMA systems