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

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

围绕环上带惩罚费用的负载均衡及相关问题进行研究，分析了问题的计算复杂性，设计出了一些多项式时间算法，并分析了近似比。