CAJ | 학술논문

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