Improved Algorithms for Weighted 3-Set Packing
加权3-Set Packing 的改进算法

Packing problems form an important class of NP-hard problems. In order to solve the weighted 3-set packing problem, this paper converts the problem to the weighted 3-set packing augmentation problem, and mainly works on how to construct a maximum weighted (k+1)-packing based on a maximum weighted k-packing. This paper gives a theoretical study on the structure of the problem and presents a deterministic algorithm of time O*(10.63k) with color-coding, which significantly improves the previous best result O*(12.83k). After further analyzing the structure of the problem and based on the set dividing method, the above result can be further reduced to O*(7.563k).