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

项目名称： 面向参数计算的随机技术研究

项目编号： No.61472449

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 冯启龙

作者单位： 中南大学

项目金额： 83万元

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

中文关键词： 随机算法；参数计算；算法设计与分析

英文摘要： 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.

英文关键词： Randomized Algorithm;Parameterized Computation;Algorithm Design and Analysis