%0 Journal Article
%T Improved Algorithms for Weighted 3-Set Packing<br>加权3-Set Packing 的改进算法
%A FENG Qi-Long
%A WANG Jian-Xin
%A CHEN Jian-Er
%A <br>冯启龙
%A 王建新
%A 陈建二
%J 软件学报
%D 2010
%I 
%X 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).
%K weighted 3-set packing
%K weighted 3-set packing augmentation
%K color-coding<br>加权3-set
%K packing
%K 加权3-set
%K packing
%K augmentation
%K color-coding
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=CFFAAB4BFB547BF89524BB3C4E44BA30&yid=140ECF96957D60B2&vid=659D3B06EBF534A7&iid=E158A972A605785F&sid=AE1A1B758F4F84BC&eid=9124D83E61CF1CD0&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=16