加权3-setpacking的改进算法

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