基于“测量治之”方法的算法设计研究

项目名称： 基于“测量治之”方法的算法设计研究

项目编号： No.61370071

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 肖鸣宇

作者单位： 电子科技大学

项目金额： 75万元

中文摘要： 测量治之方法（The Measure & Conquer Method）是2006年被提出来的一种新的算法设计与分析方法，该方法在NP难问题的精确算法设计中得到很好的应用。它从简单的算法中巧妙地抓住问题的性质从而给出改进的运行时间上界。目前很多NP难问题的最佳精确算法就是基于该方法设计的。本项目主要研究内容包括：1. 进一步研究测量治之方法中权值的约束和测量，扩充该方法的理论框架，并研究该方法在参数算法等的应用；2. 基于该方法为包括反馈集、支配集、图修改问题在内的各种基本NP难问题设计更快的算法。申请人是最早研究该方法的科研人员之一，目前已基于该方法为诸如边支配集、低度图TSP、低度图独立集等多个问题设计了当前最佳精确算法，近三年来在Algorithmica、TCS等国际重要期刊和会议上第一作者发表该方向的论文21篇。项目组在科研上很活跃，有较强理论研究基础，能承担基础科研项目。

中文关键词： 精确算法；NP难问题；图算法；分摊分析；参数算法

英文摘要： The measure-and-conquer method, firstly introduced in 2006, is a new technique that has been found great applications in the design and analysis of exact algorithms for hard problems. This method catches some good properties of the problems and then can l

英文关键词： Exact Algorithms；NP-Hard Problems；Graph Algorithms；Amortized Analysis；Parameterized Algorithms