论文部分内容阅读
Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的（k＋1）-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质：k-matching中存在2列使得该2列至少有2k/3元素被包含在（k＋1）