计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2009年
11期
1877-1884
,共8页
加权3D-matching%加权3D-matching augmentation%color-coding%动态规划%参数计算
加權3D-matching%加權3D-matching augmentation%color-coding%動態規劃%參數計算
가권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.82~(3k))的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.47~(3k))有了极大的改进.
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.82~(3k))的參數算法,最終求解加權3D-matching問題.該算法較目前文獻中的最好結果O* (5.47~(3k))有瞭極大的改進.
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.82~(3k))적삼수산법,최종구해가권3D-matching문제.해산법교목전문헌중적최호결과O* (5.47~(3k))유료겁대적개진.
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~(3k)) 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~(3k)).