精确计算和参数计算的算法新技术

项目名称： 精确计算和参数计算的算法新技术

项目编号： No.61173051

项目类型： 面上项目

立项/批准年度： 2012

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

项目作者： 陈建二

作者单位： 中南大学

项目金额： 58万元

中文摘要： 精确算法和参数算法是近二十年来发展起来的用以求解NP-难问题的方法，它引起了人们广泛的关注。为了进一步推广精确算法和参数算法在实际中的应用，开发用来设计更加快速的精确算法和参数算法的新技术就显得尤为重要。本项目将从新的角度研究精确计算和参数计算的算法新技术，并将这些技术应用到求解许多重要NP-难问题的过程中。本项目研究内容主要包括：（1）从一些具体的经典NP-难问题出发，挖掘出它们的新的量度；（2）基于图分割和组合对偶，开发出新的核心化技术；（3）结合已有的代数知识，开发新的代数技术，用以设计精确算法和参数算法。 本项目的研究成果将对如何设计高效的精确算法和参数算法起到重要作用，并对求解实际应用中的难解问题有着重大的意义。

中文关键词： 参数算法；核心化；NP难解问题；参数计算；

英文摘要：

英文关键词： Parameterized algorithm；Kernelization；NP-hard problems；Parameterized computation；