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

项目名称： 网络设计中的负载均衡问题

项目编号： No.11301466

项目类型： 青年科学基金项目

立项/批准年度： 2014

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

项目作者： 李伟东

作者单位： 云南大学

项目金额： 22万元

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

中文关键词： 负载均衡；公平分配；超图嵌入；近似算法；随机算法

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

英文关键词： Load balancing；Fair allocation；Hypergraph embedding；Approximation algorithm；Randomized algorithm