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

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

项目编号： No.11471003

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 张晓岩

作者单位： 南京师范大学

项目金额： 65万元

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

中文关键词： 图划分；超图划分；随机近似算法；随机在线算法；算法复杂性

英文摘要： 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.

英文关键词： Graph partition;Hypergraph partition;Randomized approximation algorithms;Randomized on-line algorithms;Complexity of algorithms