ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇


冯启龙 王建新 陈建二   

  1. (中南大学信息科学与工程学院 长沙 410083) (
  • 出版日期: 2009-11-15

Improved Algorithms for Weighted 3D-Matching

Feng Qilong, Wang Jianxin, and Chen Jianer   

  1. (School of Information Science and Engineering, Central South University, Changsha 410083)
  • Online: 2009-11-15

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

关键词: 加权3D-Matching, 加权3D-Matchingaugmentation, color-coding, 动态规划, 参数计算

Abstract: 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.82\+[3k}) 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.47\+{3k}).

Key words: weighted 3D-Matching, weighted 3D-Matching augmentation, color-coding, dynamic programming, parameter computation