加权3-Set Packing的改进算法

• 作者: 冯启龙 王建新 陈建二
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 加权3-set packing 加权3-set packing augmentation color-coding
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 886-898
• 分类号: TP301
• 字数: 13380字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03524

摘要

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).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	冯启龙	中南大学信息科学与工程学院	11	38	4.0	6.0