网络设计中的离散数学方法

In network design, many problems can be transferred into problems in discrete mathematics, especially in graph theory. For example, the analysis of community structure in complex networks and the circuit partitioning in the VLSI (Very Large Scale integration) design are essentially the graph/hypergraph partition problems. Furthermore, the reconstruction of complex networks may be expressed as the graph reconstruction problem. The investigation of these problems is closely related to the development of computer science, network, modern information science and technology, and has an important influence over the development of graph theory. The applicants have been working on graph theory, algorithms, and related applications, achieving a series of important results. In some areas, they hold an internationally leading position. In this project, the applicants will investigate some problems in network design, using discrete mathematics methods, especially graph theory methods. More precisely, we will improve the partition theory of graph/hypergraph, which will be used to establish the theoretical basis of community analysis in complex network, obtain effective algorithms for community analysis and circuit partitioning, and reconstruct complex networks by compressed sensing method. Our goal is to make some major breakthroughs both on theory and methods in the investigations of the above-mentioned problems and significantly promote such investigations. Another goal is to strengthen the academic exchanges domestically and internationally and to establish a strong team with talented young researchers. The success of the project will promote the reputation of our country in the international graph theory community.

网络设计中的许多问题都可以转化为离散数学问题, 尤其是图论问题, 例如复杂网络的社团分析、大规模集成电路的划分问题都可以转化成图/超图的划分问题, 复杂网络的重构问题可以表示成图的重构问题, 这些问题的研究不仅与计算机学科、网络、现代信息科学与技术等学科的发展密切相关, 并对之产生重要影响, 而且在图论中具有影响整个学科发展的重要地位. 本课题申请人和研究人员长期从事图论与算法及其应用领域研究工作,取得了一系列的研究成果, 在不少问题的研究进展方面保持着国际领先的地位. 本项目主要利用离散数学方法, 尤其是图论方法, 对网络设计中的几个主要问题进行研究. 包括完善图划分理论, 利用现代图/超图划分理论建立复杂网络社团结构分析理论基础, 设计社团划分和大规模集成电路划分的有效算法, 利用压缩感知理论重构复杂网络.在理论和方法上取得较大突破.对相关问题的研究起到实质性的推动作用.

本项目围绕网络设计中的离散数学问题, 主要从事图论领域的基础研究和大规模集成电路设计领域的应用研究。Tutte为研究四色问题创立了整数流理论，我们以整数流为工具研究Alon提出的圈覆盖猜想，将整数流最新成果应用于圈覆盖问题，取得重要进展，为Alon-Tarsi猜想的研究提供了新思路。现实世界中的网路中基本上不具有“严格”的随机性，而具有所谓的拟随机性。我们的研究工作很大一部分是有关社交网路的离散结构进行的。我们证明了很多现实世界网络的聚集系数都近似于d/n,其中 d是平均度,n是点数。而对于小世界网络的产生机理，我们建立一个模型，模拟小世界网络的产生。. 点集划分问题是图论研究的一个重要研究方向。我们将概率方法和结构分析相结合，解决了Bollobas关于公平划分的一个猜想。在超图划分研究方面，我们首次引入超图的移点技术。在有向图划分问题上，我们也取得了若干重要成果。我们证明了Bollobas平衡划分猜想：每一个有m条边且最小度至少为2的图有一个平衡划分使得两个子集各自导出一个边数不超过m/3的子图，且刻画出了唯一的极图。在大规模集成电路设计领域，我们研究了多倍行高标准单元布局合法化问题，设计了快速近优合法化算法，获DAC’17最佳论文奖，系该会54年来中国大陆学者首次以第一单位/第一作者获得最佳论文奖。构造了VLSI全局布局问题的基于泊松方程的快速求解方法，获ICCAD’18最佳论文奖提名。我们提出了广义增广拉格朗日方法，该方法保留了二次罚方法和增广拉格朗日法的优点，并将二次罚方法平滑地过渡到了增广拉格朗日法，可以解决在许多领域都有广泛的应用的一般大规模非线性优化问题。研究了集成电路制造设计中的三重图样光刻版图分解问题，提出了离散松弛理论和算法框架，并用于解决自组装和三重图样光刻技术下通孔层分解问题以及混合电子束和三重图样光刻技术版图分解问题等。