网络设计中的负载均衡问题

Network design problem satisfying the given connectivity requirements is an important problem in combinatorial optimization. In general graph, the network design problem under the objective of minimizing the maximum load is NP-hard, where the load of a vertex is the norm of the vector which is equal to the sum of the weighted vectors of the edges adjacent to it. In this project, we will consider this problem on special graphs including series-parallel graph, Halin graph, cubic graph and directed acyclic graph. We will analysis its computational complexity and present optimal algorithms or approximation algirhtms whose running time is polynomial. Also, we will study the fixed parameter cases, and present some fixed parameter optimal algorithms when the treewidth, maximum degree or optimal value is fixed. The problem of embedding a weighted hypergraph in a cycle is NP-hard and can be approximated within 1.5. We will study a generalized version, where each hyperedge has a weighted vector and the load of a link in the cycle is the norm of the vector which is the sum of the vectors of the hyperedges whose embedding use it. We will construct a mathematical programming for this problem to design a polynomial time algorithm with good approximation ratio. The idea of the algorithm will be extended to the related optimization problems.

满足连通性需求的网络设计问题是组合最优化领域重要的问题之一。 在一般图上，以最小化最大顶点负载为目标函数的此类问题是NP困难的, 这里顶点负载定义为与之关联的边的负载向量之和的范数。本项目拟考虑特殊图(如系列平行图、哈林图、立方图和无圈图等)上的情形，分析其计算复杂性并给出多项式时间最优算法或近似算法。同时，考虑固定参数的情形，拟给在树宽、最大度和最优值为固定参数时的最优算法。 环上赋权有向超图嵌入问题是NP-难的并存在一个1.5-近似算法。本项目还打算研究一个推广的环上赋权超图嵌入问题， 即每条超边赋有一个k-维的权重向量, 环中的连接边的负载定义为用过该连接边的超边的权重向量之和的范数。拟建立此问题的数学规划模型，并给出近似比较好的多项式时间算法，并将算法思想应用到相关优化问题中去。

网络设计和负载均衡问题是组合最优化领域重要的基本问题。给定一个网络，负载通常定义在边或点上，如何实现点或边上的负载均衡是许多应用领域(如资源调度)关注的主要问题之一。由于一般网络中的负载均衡问题难以得到近似性能较好的算法，本项目主要考虑二部图、环和路等特殊网络中的负载均衡问题。项目中结合了网络结构和调度理论提出了一系列新的数学模型，利用复杂性理论分析问题的计算困难性，采用数学规划、图论或概率论等工具设计相关优化问题的多项式时间最优算法、近似算法或随机算法。取得了若干具有重要意义的科研成果，达到了预期目标。目前，已正式发表9篇期刊论文和6篇会议论文。项目组中有2名成员顺利取得博士学位，目前还有2名博士研究生和2名硕士研究生在读。