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

结题报告

项目介绍

AI项目解读

基本信息

批准号：
61370071
项目类别：
面上项目
资助金额：
75.0万
负责人：
肖鸣宇
依托单位：
电子科技大学
学科分类：
F0201.计算机科学的基础理论
结题年份：
2017
批准年份：
2013
项目状态：
已结题
起止时间：
2014-01-01 至2017-12-31

项目参与者：
Hiroshi Nagamochi；钟秀琴；池水明；余盛季；孙鹏；吕娜；张西洋；程呈；何雄；
关键词：
图算法精确算法参数算法 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 lead simple and improved algorithms. Currently, many best exact algorithms for basic NP-hard problems are designed with this method. In this project, we plain to do: 1. fruit this new method by establishing some theories for the constraints on the 'weights' and the way how to identify the best weights, and investigate how to combine this method with other techniques to design parameterized algorithms and so on; 2. based on the method, design improved algorithms for some basic NP-hard problems, such as Feedback Set, Dominating Set and Graph Modification problems. The applicant has investigated the measure-and-conquer method for many years and is quite familiar with it, and has designed the current best exact algorithms for Edge Dominating Set, TSP in low-degree graphs, Independent Set in low-degree graphs and some other basic NP-hard problems. More than 20 papers under the applicant's name have been published in Algorithmica and other journals or conferences in this area. The background of the research group should be strong enough to achieve this project.

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

结项摘要

本项目对“测量治之”方法进行了深入研究并形成了系列科研成果，截止2017年12月已经发表了资助论文32篇和论文集1本。发表的论文中有15篇为国际SCI期刊论文，15篇为国际会议论文，剩下2篇则发表在中文计算机学报和软件学报上。按CCF分区类来算，其中4篇A类，7篇B类，9篇C类。值得说明的是32篇已发表论文中28篇为第一标注项目基金号。..该项目在“测量治之”技术上进行了多方面的深入研究，提出了新的测量对象——非顶点加权的概念以及“shift”的分摊分析概念，利用这些新方法将“测量治之”技术应用到TSP等以前未能应用的问题上，从而开拓了该技术的应用场景。基于新的算法设计技巧，该项目为最大独立集、反馈集、子集反馈集、最大导出匹配、k-plex、3路径点覆盖、低度图上的TSP、支配导出匹配等基本NP难问题设计设计了当前最佳的精确算法。部分具体结果列举如下：.1. 最大独立集问题：设计了运行时间为O(1.1996^n)的多项式内存空间算法，改进了1986年Robson给出的O(1.2109^n)的指数空间算法，打破了Fomin等人提出的1.2^n这个界限；.2. 最大导出匹配问题：将原有时间上界O(1.4786^n)改进到了O(1.3752^n)；.3. 反馈顶点集问题：将原有时间上界O(1. 7548^n)改进到了O(1.7266^n)；.4. 子集反馈顶点集问题：将原有时间上界O(1.8638^n)改进到了O(1. 7743^n)；.5. 3度图和4度图上的TSP问题：分别给出了新的运行时间上界O(1. 2312^n)和O(1.692^n)；.6. 3路径点覆盖问题：将原有时间上界O(1. 4658^n)改进到了O(1.3659^n)；.7. 支配导出匹配问题：给出了运行时间为O(1.1467^n)的算法，大大改进了已知各个算法；.8. K-plex问题：第一次打破了穷举搜索时间界O(2^n)，对于每个给定的k，得到一个运行时间为O(c^n)的算法，其中c是一个严格小于2的常数。