加权3-Set Packing的改进算法

摘要：

Packing问题构成了一类重要的NP难问题.对于加权3-Set Packing问题,把问题转化成加权3-Set Packing Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).

关键词：加权3-set packing、加权3-set packing augmentation、color-coding

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

资助基金：the National Natural Science Foundation of China under Grant Nos.60433020, 60773111;the National Basic Research Program of China under Grant No.2008CB17107 国家重点基础研究发展计划973;the Program for New Century Excelent Talents in University of China under Grant No.NCET-05-0683;the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0661 长江学者和创新团队发展计划

在线出版日期：2010-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：886-898