面向参数计算的随机技术研究

As an efficient method solving NP-hard problems, random methods in Parameterized Computation have attracted lots of attention, which have been used to design parameterized algorithms for many hard problems. However, many aspects of random methods in parameterized computation are just at the beginning research status, and more efforts are needed. This project is focused on the randomized techniques in parameteried computation. Firstly, we study the randomized technique based on solution structure of hard problems. Then, for hard problems, by making full use of operations in the problems, we study random methods based on the randomly handling of the operations. Moreover, we study the kernelization analysis of hard problems from the random perspective, and study the combination application of traditional algorithm techniques and random methods in parameterized computation. Finally, the derandomized methods for randomized techniques are studied. The objective of this project is to get systematic study of random methods in parameterized computation, aim of providing new techniques for hard problems, improving the efficiency of parameterized algorithms and promoting the development of corresponding fields.

作为有效求解难解问题的手段，随机方法近年来在参数计算领域受到了人们的关注。许多难解问题基于随机方法都得到有效求解，但随机方法在参数计算领域各个方面的研究正处于起步阶段，都待进一步发展和完善。 本项目将研究面向参数计算领域的随机技术。首先研究基于问题解空间特性的随机技术，基于问题基本操作的随机技术和基于随机方法的核心化分析技术；然后研究传统算法技术与随机方法在参数计算领域的综合应用；最后研究参数计算随机方法确定化方法。本项目的研究旨在建立求解各类难解问题的相应随机技术，为应用领域中的难解问题求解提供新的思路，继而推动相应领域的发展。

在本基金的资助下，课题组针对P2-Packing、k-means聚类、最大可满足性等一系列经典难解问题的参数算法、随机算法、核心化算法以及近似算法展开研究，并在资源调度和生物信息等领域得到有效应用。主要成果如下：1. 深入分析难解问题解空间结构，基于操作的随机处理与参数计算的随机分析，提出了P2-Packing、加权P3-Packing以及Co-Path Set等问题的随机参数算法。提出了关于受限k-means聚类问题运行时间最短的(1+ε)-近似算法；2. 研究难解问题的核心化算法。改进了最大内部节点生成树、最大对分、最大环-Packing等一系列经典难解问题的最好核心化结果；分析局部简化技术，并运用此技术提出了关于Co-Path Set、G7图上的支配集和路径收缩等问题的核心化算法；3. 研究影响难解问题的关键参数，提出了近似森林删除、簇图修改、子图同构等一些经典图修改问题以及可满足性问题的改进参数算法；为系谱比较与系统发生树等生物信息学领域中的常用工具建立参数模型，并给出有效的参数算法；4. 提出了近似森林删除、最大内部节点生成树以及一些调度问题的近似算法。