Set Packing问题的研究进展

Set Packing问题起源于分割问题的应用，是在强约束条件对元素进行划分。在复杂性理论中，此问题是一类重要的NP难问题，被广泛应用于调度、代码优化和生物信息学等领域。特别是在参数计算理论产生后，此问题再次成为研究的热点问题。依据所研究问题的差异，本文将Set Packing问题分成5类，并给出了具体的定义。在此基础上，分别介绍了求解这5类问题的相关算法，着重分析和比较了参数算法中所运用的各项技术，并提出了该问题算法研究的一些发展方向。

Algorithms for Set Packing: A Survey

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.