加权3D‐Matching 的改进算法

摘要：

Matching 问题构成了一类重要的NP 难问题。近年来，局部贪婪、着色、动态规划和随机分治法等多种技术被用来设计参数化matching 问题的算法。对于加权3D-Matching 问题，本文把问题转化成加权3D-Matching Augmentation 问题进行求解，即主要讨论怎样从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing，通过对(k+1)-packing 结构的进一步分析，从问题的特殊结构特性出发，给出了加权3D-Matching 问题特有的性质。基于给出的性质，运用Color-Coding技术，给出了一个时间复杂度为O*(4.823k)的参数算法，该算法较目前文献中的最好结果O*(5.473k)有了极大的改进。

关键词： Weighted 3D-Matching 3D-Matching Augmentation Dynamic Programming

作者: 冯启龙 陈建二 王建新

会议类型: 国内会议

会议名称: 湖南省第三届研究生创新论坛——信息与控制工程的新理论和新技术分论坛

会议地点: 长沙

会议语种:中文

页码: 61-67

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