基於“測量治之”方法的算法設計研究

《基於“測量治之”方法的算法設計研究》是依託電子科技大學,由肖鳴宇擔任醒目負責人的面上項目。

基本介紹

• 中文名：基於“測量治之”方法的算法設計研究
• 依託單位：電子科技大學
• 項目類別：面上項目
• 項目負責人：肖鳴宇

項目摘要

測量治之方法（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的常數。