负载平衡问题是组合最优化领域中的热点问题之一,其目标函数通常有三类：最小化最大负载(简记为min-max)、最大化最小负载(简记为max-min)和最小化负载向量的lp-范数(简记为min-lp).本论文设计出了这三类目标函数下带各类约束的负载平衡问题的一些近似算法.本论文同时还研究了与负载平衡问题相关的推广的装箱问题和网络中的最小费用插点问题.全文分为十章：第一章介绍了研究的背景、基本定义和本论文的主要研究成果.第二章研究了等级约束下的负载平衡问题.当目标函数为min-max时,设计出了服务等级标号数为2的情形下的一个有效的多项式时间近似方案(简记为EPTAS),部分地解决了Ou等人[83]提出的问题,并设计出机器数为常数情形下的一个简单的运行时间为O(n)的全多项式时间近似方案(简记为FPTAS)；当目标函数为max-min时,设计出了一般情形下的多项式时间近似方案(简记为PTAS),服务等级标号数为常数情形下的一个EPTAS,机器数为常数情形下的一个运行时间为O(n)的FPTAS;当目标函数为min-lp时,设计出了一个对所有p都成立的2-近似算法,并设计出了机器数为固定常数的情形下的一个运行时间为O(n)的FPTAS.第三章研究了带数目约束的负载平衡问题.当目标函数为min-max时,证明了2-半匹配问题是3/2-ε不可近似的(这里ε>0),并设计出一个2-近似算法；当目标函数为max-min时,证明了2-半匹配问题是1/2+ε不可近似的(这里ε>0),并设计出一个1/2-近似算法；当目标函数为min-lp时,证明了2-半匹配问题是APX-难的,并设计出了一个2p-1/p-近似算法.第四章研究了划分拟阵约束下的负载平衡问题.当目标函数为min-max时,设计出了k为固定常数情形下的一个EPTAS和m为固定常数情形下的一个FPTAS;当目标函数为max-min时,设计出了一般情形下的一个击1/k-1-近似算法,k为固定常数情形下的一个EPTAS和m为固定常数情形下的一个FPTAS;当目标函数为min-lp时,设计出了一个全范数2-近似算法,从而推广了Wu和Yao[99]的结果,并设计出了m为固定常数情形下的一个FPTAS.第五章研究了拒绝费用受限的负载平衡问题.当目标函数为min-max时,设计出了一个PTAS,并设计出了机器数为固定常数的情形的一个运行时间为O(n2)的FPTAS,这改进了文献[4,105]中的结果；当目标函数为min-lp时,设计出了机器数为固定常数的情形下的一个FPTAS.第六章研究了带机器准备时间的负载平衡问题.当目标函数为min-max时,设计出了一个EPTAS,并设计出了机器数为固定常数的情形的一个运行时间为O(n)的FPTAS;设计出了一个通用目标函数下运行时间为O(n)的的EPTAS,推广了Alon等人[3]的结果.第七章研究了环上的负载平衡问题.证明了带拒绝费用的环上的负载平衡问题在流量可分的情形下依然是NP-难的,设计出了流量不可分的情形下了一个3-近似算法和流量可分的情形下的一个i/e-1-近似算法；利用一种新的取整技巧设计出了混合环上有向超图嵌入问题的一个2-近似算法；设计出了赋权环上有向超图嵌入问题的一个PTAS,从而推广了Li和Wang [76]的结果.第八章研究了两个推广的装箱问题.证明了拒绝费用受限的装箱问题是2-ε不可近似的,并设计出一个2-近似算法；设计出了凹费用装箱问题的一个运行时间为O(n)的渐近的多项式时间近似方案(简记为APTAS)和一个渐近的全多项式时间近似方案(简记为AFPTAS),从而解决了Leung和Li[71]提出的两个问题.第九章研究了网络中的插点问题.证明了(s,U)-插点问题是(1-ε)lnn-不可近似的,除非NP(?)TIME(nO(loglogn));证明了路上插点问题多项式等价于限制性的最短路问题,并设计出了一个新颖的动态规划算法来求得单位插点费用相同情形下的最优解；证明了树上插点问题多项式等价于限制性的最小支撑树问题,并设计出一个特殊情形下的最优算法.第十章对全文进行了总结并提出了二十个问题,为未来的研究指明了方向.
