东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

加权3D-Matching的改进算法

期刊名称：计算机研究与发展
时间：0
页码：1877-1884
语言：中文
分类：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
作者机构：[1]中南大学信息科学与工程学院,长沙410083
相关基金：基金项目：国家“九七三”重点基础研究发展计划前期研究专项基金项目（2008CB317107）;国家自然科学基金项目（60773111,60873265）,长江学者和创新团队发展计划基金项目（IRT0661）
相关项目：基于网络编码的无线网络安全性与可靠性研究

关键词：加权3D-matching, 加权3D-matching, augmentation, color-coding, 动态规划, 参数计算, weighted 3D -matching, weighted 3D -matching augmentation, color-coding, dynamic programming, parameter computation

中文摘要：

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）有了极大的改进.

英文摘要：

Matching problem is an important class of NP-hard problems, which has great applications in many fields, such as scheduling and code optimization etc. This paper mainly focuses on the weighted 3D-matching problem, and gives further analysis for the structure of the problem. In order to solve the weighted 3D-matching problem more efficiently, the weighted 3D-matching problem is converted to the weighted 3D-matching augmentation problem, which is to construct a maximum weighted （k＋ 1）-matching based on a maximum weighted k-matching. The authors firstly provides further theoretical study on the structure of the weighted 3D-matching augmentation problem and present some special properties of the problem. For the weighted 3D-matching augmentation problem and for a given maximum weighted k-matching of the instance, there must exist two columns in this maximum weighted k-matching such that at least 2k/3 elements Of those two columns are contained in the corresponding columns in maximum weighted （k＋1 ）-matching. On the basis of those special properties and by using color-coding and dynamic programming techniques, an improved parameterized algorithm with time complexity O＊（4.823k） is given. The above improved algorithm results in an improved parameterized algorithm for the weighted 3D-matching problem, which significantly improves the previous best result O＊（5.473k）.

同期刊论文项目