Packing problems form an important class of NP-hard problems. For the weighted 3-Set Packing problem, we provide further theoretical study on the problem and present a deterministic algorithm of time O~*(10.6~(3k)). Based on the randomized divide-and-conquer method, the above result can be further reduced to O~*(7.56~(3k)), which significantly improves the previous best result O~*(12.8~(3k)).
展开▼
