负载平衡及网络构建问题

《负载平衡及网络构建问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、扉页：独创性2声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人或集体已经发表或撰写过的研究成果，对本文的研究做出贡献的集体和个人均已在论文中作了明确的说明并表示了谢意。研究生签名：论文使用和授权说明本人完全了解云南大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵循此规定)研

2、究生签名：叫兰扣导师签名日期：望旦：±主』本人及导师同意将学位论文提交至清华大学“中国学术期刊(光盘版)电子杂志社”进行电子和网络出版，并编入CNKI系列数据库，传播本学位论文的全部或部分内容，同意按《中国优秀博硕士学位论文全文数据库出版章程》规定享受相关权益。研究生签名：——导师签名：日期：摘要负载平衡问题是组合最优化领域中最经典的问题之一，它在网络设计、资源分配、工业管理及信息传播等问题中有着非常广泛的应用。经典的负载平衡问题是ⅣP一难的，该问题已经得到了较好地研究。在过去几十年中，出现了许多推广与变形的负载平衡问题，

3、这些问题吸引了众多研究学者的关注。网络构建问题也是近年来的一个研究热点，它主要研究合理地构建各种网络，比如光纤网络、通信网络和供电网络等。本论文对一些现有的负载平衡问题和网络构建问题进行研究和推广，其宗旨是为了提出更加贴近实际的模型，设计出解决相应优化问题的一些近似算法。全文分为七章内容：第一章介绍了ⅣP-完备问题的研究背景、负载平衡问题和网络构建问题的研究现状以及本论文得到的主要研究成果。第二章介绍了关于图论、组合最优化、近似算法和博弈论方面的一些相关预备知识。第三章研究了有向环上带拒绝费用负载平衡问题。当流量可分时，证

4、明了该问题是NP一难的，并设计了一个1．58一近似算法；当流量整数可分时，通过取整的方法，同样得到一个1．5&近似算法；当流量不可分时，设计了一个3一近似算法和一个(1．58+E)一近似算法。第四章研究了带拒绝费用呼叫控制问题(简记为PCCC问题)。证明了在路径图上PCCC问题是ⅣP-难的，从而在一般图上该问题也是ⅣP-难的：在路径图和星图上，当所有呼叫的流量为l时，分别设计了相应的多项式最优算法；在环上，当所有呼叫的流量为1且拒绝费用为常数时，设计了～个多项式最优算法，当所有呼叫的流量为1时，给出了该问题的一个多项式时间

5、近似方案(简记为PTAS)；在一般图上，通过线性规划取整的方法设计了PCCC问题的一个2一近似算法，再利用随机取整的技巧得到一个1．58一近似算法。第五章研究了网络构建问题。对于一般网络构建问题，证明了该问题是(2一￡)不可近似的，并设计了两个渐进近似算法，近CASk分别为2Q和孕，其中乜为解决ll基于组合结构P的最小化问题的某个近似算法的近似比；对于支撑树构建问题，证明了该问题是(1．5一￡)一不可近似的，并设计了一个1．5一近似算法；对于最小路径树构建问题，证明了该问题是(1．5一￡)一不可近似的，并设计了一个1．5一

6、近似算法。第六章研究了等级约束下负载平衡博弈。考虑了Makespan和LG—LPT两种协调机制，在Makespan机制下，当m=2时，POA=1．5，当7Tt>2时，POA为e(』log!l业ogLm)；在LG—LPT机制下，当m=2时，POA=互5，当仇>2时，POA=2一士。另外还分析了在LG—LPT机制下纳什均衡的收敛性。第七章总结了上述工作，并对未来工作进行了展望。关键词：负载平衡；网络构建；ⅣP一难；近似算法；无序价格(POA)AbstractLoadbalancingproblemisoneofthemostc

7、lassicresearchtopicsincombina-torialoptimization，whichisappliedwidelyinnetworkdesign，resourceassignment，industrialmanagement，informationtransmissionandSOon．Theclassicloadbal—ancingproblemisNP—hardandhasbeenstudiedwell．Inthepastfewdecades．alotofgeneralizedandvarian

8、tloadbalancingproblemshavebeenposedandattractedmanyattentionsoftheresearchers．Networkconstructingproblemisalsoanactiveresearchtopicintherecentyears．Thep