網路設計中的離散數學方法

《網路設計中的離散數學方法》是依託福州大學，由范更華擔任項目負責人的重點項目。

基本介紹

• 中文名：網路設計中的離散數學方法
• 依託單位：福州大學
• 項目類別：重點項目
• 項目負責人：范更華

項目摘要

網路設計中的許多問題都可以轉化為離散數學問題, 尤其是圖論問題, 例如複雜網路的社團分析、大規模積體電路的劃分問題都可以轉化成圖/超圖的劃分問題, 複雜網路的重構問題可以表示成圖的重構問題, 這些問題的研究不僅與計算機學科、網路、現代信息科學與技術等學科的發展密切相關, 並對之產生重要影響, 而且在圖論中具有影響整個學科發展的重要地位. 本課題申請人和研究人員長期從事圖論與算法及其套用領域研究工作,取得了一系列的研究成果, 在不少問題的研究進展方面保持著國際領先的地位. 本項目主要利用離散數學方法, 尤其是圖論方法, 對網路設計中的幾個主要問題進行研究. 包括完善圖劃分理論, 利用現代圖/超圖劃分理論建立複雜網路社團結構分析理論基礎, 設計社團劃分和大規模積體電路劃分的有效算法, 利用壓縮感知理論重構複雜網路.在理論和方法上取得較大突破.對相關問題的研究起到實質性的推動作用.

結題摘要

本項目圍繞網路設計中的離散數學問題, 主要從事圖論領域的基礎研究和大規模積體電路設計領域的套用研究。Tutte為研究四色問題創立了整數流理論，我們以整數流為工具研究Alon提出的圈覆蓋猜想，將整數流最新成果套用於圈覆蓋問題，取得重要進展，為Alon-Tarsi猜想的研究提供了新思路。現實世界中的網路中基本上不具有“嚴格”的隨機性，而具有所謂的擬隨機性。我們的研究工作很大一部分是有關社交網路的離散結構進行的。我們證明了很多現實世界網路的聚集係數都近似於d/n,其中 d是平均度,n是點數。而對於小世界網路的產生機理，我們建立一個模型，模擬小世界網路的產生。點集劃分問題是圖論研究的一個重要研究方向。我們將機率方法和結構分析相結合，解決了Bollobas關於公平劃分的一個猜想。在超圖劃分研究方面，我們首次引入超圖的移點技術。在有向圖劃分問題上，我們也取得了若干重要成果。我們證明了Bollobas平衡劃分猜想：每一個有m條邊且最小度至少為2的圖有一個平衡劃分使得兩個子集各自導出一個邊數不超過m/3的子圖，且刻畫出了唯一的極圖。在大規模積體電路設計領域，我們研究了多倍行高標準單元布局合法化問題，設計了快速近優合法化算法，獲DAC’17最佳論文獎，系該會54年來中國大陸學者首次以第一單位/第一作者獲得最佳論文獎。構造了VLSI全局布局問題的基於泊松方程的快速求解方法，獲ICCAD’18最佳論文獎提名。我們提出了廣義增廣拉格朗日方法，該方法保留了二次罰方法和增廣拉格朗日法的優點，並將二次罰方法平滑地過渡到了增廣拉格朗日法，可以解決在許多領域都有廣泛的套用的一般大規模非線性最佳化問題。研究了積體電路製造設計中的三重圖樣光刻版圖分解問題，提出了離散鬆弛理論和算法框架，並用於解決自組裝和三重圖樣光刻技術下通孔層分解問題以及混合電子束和三重圖樣光刻技術版圖分解問題等。