Improved Algorithms for Weighted 3-Set Packing
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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). by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
