信息科学中图与超图划分问题的随机近似算法研究

Graph partitioning problems have a wide range of applications in bio-informatics, computer science and engineering management. Hypergraph partitioning problems are one of the fundamental problems in hypergraph theory. Such problems have more complex and abstract structures than those raised in graph model.And hypergraph partitioning problems can provide a more accurate mathematical model in many actual demands coming from information sciences generally. Many graph and hypergraph partitioning problems which can be applied in information science are NP-hard and even difficult to be approximated. So it is important to investigate the problems from the algorithmic perspectives in the intersection of mathematics and computer science. However, it is always very difficult to design good algorithms for such problems only by structural methods due to their complex structures. Especially,we study some kinds of graph and hypergraph partitioning problems raising from information science,which are Limited capacity cluster bottlenecks partition, Graph balanced storage partition and Judicious partition, Restricted hypergraph list coloring and Randomized hypergraph on-line coloring. We focus on the these problems for design, analysis and experiment of their randomized approximation algorithms and randomized on-line algorithms. Generally,it requires more techniques from other areas of mathematics, for instance, the methods and tools in mathematical programming, high-dimensional geometry and probability.Moreover, the research on making use of the randomized rounding methods based on linear and semidefinite relaxation, Lováse local lemma and partial first-fit, etc.for solving the discrete optimization problems with abstract structures is complex and challenging.The substantive progress in this aspect of study has important significance in both theoretic and applications.

图划分问题是图论中的一个基本问题，在生物信息学、计算机科学以及工程管理等领域都有着非常广泛的应用。该问题的推广，超图划分问题，比图划分问题更加复杂，并且在信息科学中提供了比图划分更精确的数学模型。由于大部分图与超图划分问题都是NP困难的甚至难近似的, 一般都具有较为抽象的组合结构，所以很难仅从结构分析的角度得到解决。本课题选择几类在信息科学中有重要应用价值的图与超图划分问题，即有容量限制的聚类瓶颈划分、图的均衡存储划分和公平划分、超图的有限制列表染色和在线染色，开展这些问题的随机近似算法和在线算法的设计、分析和实验研究。研究中将充分利用数学规划、高维几何及随机分析等领域的知识，发展基于线形规划和半正定规划松弛的随机舍入方法、Lováse 局部引理等概率分析技巧以及Partial First-Fit等递归方法，期望在这些问题求解随机算法方面得到突破，研究实质进展具有重要的理论意义和应用价值。

图与超图优化划分问题是网络设计及优化领域里的基础性问题，并且许多重要的图优化划分问题都是NP困难的甚至难近似的，在并行计算、大规模集成电路设计、图像识别以及大规模复杂网络的有效存储上都具有非常重要的应用，因此从图的结构和算法方面对图优化问题进行研究在数学与计算机科学的交叉领域特别是信息网络科学中里占有极其重要的位置。 课题组选择在信息科学中有重要应用价值的若干图与超图划分问题及超图张量谱理论在超图划分应用等方面开展这些问题的结构研究以及随机算法和近似算法等方面的设计、分析和实验研究。近似算法和随机算法相比于精确算法具有简单实用和高效快速等优点，在实践中更为适用于解决数学与计算机科学交叉领域中出现的一些大规模的NP困难问题。在已取得的研究成果中课题组充分利用了图论、数学规划及随机分析等领域的知识和基于线形规划和半正定规划松弛等随机舍入方法深入研究了这些问题的极值特性以及在求解近似算法和随机算法方面获得了重要进展，文章发表在《Siam Journal of Scientific Computing 》和《Siam Journal of Discrete Mathematics》等有影响力的重要SCI期刊上，并撰写了英文专著一部，研究实质进展具有重要的理论意义和应用价值。