加权3D-Matching的改进算法

摘要：

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的(k+1)-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质: k- matching中存在2列使得该2列至少有2k/3元素被包含在(k+1)-matching中所对应的2列中.基于给出的性质,通过运用color-coding和动态规划技术,给出了一个时间复杂度为O* (4.823k)的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.473k)有了极大的改进.

关键词：加权3D-matching、加权3D-matching augmentation、color-coding、动态规划、参数计算

所属期刊栏目：46

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

资助基金：国家"九七三"重点基础研究发展计划前期研究专项基金项目2008CB317107;国家自然科学基金项目60773111,60873265;长江学者和创新团队发展计划基金项目IRT0661

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

页数：共8页

页码：1877-1884