环上带惩罚费用的负载问题

项目名称： 环上带惩罚费用的负载问题

项目编号： No.11126315

项目类型： 专项基金项目

立项/批准年度： 2012

项目学科： 轻工业、手工业

项目作者： 李伟东

作者单位： 云南大学

项目金额： 3万元

中文摘要： 环上带惩罚费用的负载问题的定义为：给定一个包含n个顶点的环和m个赋权的点对，可以选择不连接点对，但要付出相应的惩罚费用。连接某些点对，使得没有连接的点对的惩罚费用总和与环上的边的最大负载之和尽可能地小。项目申请人在博士论文里利用线性规划理论给出了一个3-近似算法，后来又结合随机算法给出了一个1.58-近似算法。本项目拟建立此问题的凸规划模型，结合随机算法和Schrijver等人的线性规划取整技巧得到此问题的一个近似比更好的多项式时间算法。同时采用NP完备性理论、参数复杂性理论和PCP理论给出此问题的不可近似比。在此基础上，我们拟将研究成果推广到赋权环上带惩罚费用的负载问题和环上带惩罚费用的超图嵌入问题。本项目将培养研究生2-3名，在国内外重要期刊上发表2-3篇论文，为环上相关问题的研究提供理论依据。

中文关键词： 负载均衡；计算复杂性；近似算法；；

英文摘要：

英文关键词： Load balancing；Computational complexity；Approximation algorithm；；