Set Packing问题的研究进展  

Algorithms for Set Packing:A Survey

作　　者：马振宇[1] 王建新[1] 冯启龙[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2007年第9期12-15,22,共5页Computer Science

基　　金：国家自然科学基金重点项目:生物信息学中的相关组合理论和算法研究(60433020)

摘　　要：Set Packing问题起源于分割问题的应用,是在强约束条件对元素进行划分。在复杂性理论中,此问题是一类重要的NP难问题,被广泛应用于调度、代码优化和生物信息学等领域。特别是在参数计算理论产生后。此问题再次成为研究的热点问题。依据所研究问题的差异,本文将Set Packing问题分成5类,并给出了具体的定义。在此基础上,分别介绍了求解这5类问题的相关算法,着重分析和比较了参数算法中所运用的各项技术,并提出了该问题算法研究的一些发展方向。Set packing problem is originated from the application of cutting problem which is to divide the elements under strong constraint condition. In complexity theory, set packing problems is an important NP-hard problem, which is used widely in the fields of scheduling and code optimization. Especially after the emerging of the parameterized computation theory, set packing problem becomes one of the most concerned research problem. According to the differences of the concerned problem, we divide the set packing problem into five classes and give the corresponding definition. This paper gives a detailed presentation of all the current algorithms for the problems of the five classes, and puts emphasis on the analysis and comparison of the technique used in those parameterized algorithms. At last, we present some development orientation in algorithm research for the set packing problem.

关 键 词：SET PACKING问题 NP难问题 复杂性理论 参数计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]