负载平衡问题是组合最优化领域中最经典的问题之一，它在网络设计、资源分配、工业管理及信息传播等问题中有着非常广泛的应用。经典的负载平衡问题是NP-难的，该问题已经得到了较好地研究。在过去几十年中，出现了许多推广与变形的负载平衡问题，这些问题吸引了众多研究学者的关注。　　网络构建问题也是近年来的一个研究热点，它主要研究合理地构建各种网络，比如光纤网络、通信网络和供电网络等。　　本论文对一些现有的负载平衡问题和网络构建问题进行研究和推广，其宗旨是为了提出更加贴近实际的模型，设计出解决相应优化问题的一些近似算法。　　全文分为七章内容:　　第一章介绍了NP-完备问题的研究背景、负载平衡问题和网络构建问题的研究现状以及本论文得到的主要研究成果。　　第二章介绍了关于图论、组合最优化、近似算法和博弈论方面的一些相关预备知识。　　第三章研究了有向环上带拒绝费用负载平衡问题。当流量可分时，证明了该问题是NP-难的，并设计了一个1.58-近似算法;当流量整数可分时，通过取整的方法，同样得到一个1.58-近似算法;当流量不可分时，设计了一个3-近似算法和一个(1.58+ε)-近似算法。　　第四章研究了带拒绝费用呼叫控制问题（简记为PCCC问题）。证明了在路径图上PCCC问题是NP-难的，从而在一般图上该问题也是NP-难的;在路径图和星图上，当所有呼叫的流量为1时，分别设计了相应的多项式最优算法;在环上，当所有呼叫的流量为1且拒绝费用为常数时，设计了一个多项式最优算法，当所有呼叫的流量为1时，给出了该问题的一个多项式时间近似方案（简记为PTAS）;在一般图上，通过线性规划取整的方法设计了PCCC问题的一个2-近似算法，再利用随机取整的技巧得到一个1.58-近似算法。　　第五章研究了网络构建问题。对于一般网络构建问题，证明了该问题是（2-ε）不可近似的，并设计了两个渐进近似算法，近似比分别为2α和7α/4，其中α为解决基于组合结构P的最小化问题的某个近似算法的近似比;对于支撑树构建问题，证明了该问题是(1.5-ε)-不可近似的，并设计了一个1.5-近似算法;对于最小路径树构建问题，证明了该问题是(1.5-ε)-不可近似的，并设计了一个1.5-近似算法。　　第六章研究了等级约束下负载平衡博弈。考虑了Makespan和LG-LPT两种协调机制，在Makespan机制下，当m=2时，POA=1.5，当m＞2时，POA为(⊙)（logm/loglogm）;在LG-LPT机制下，当m=2时，POA=5/4，当m＞2时，POA=2-1/(m-1)。另外还分析了在LG-LPT机制下纳什均衡的收敛性。　　第七章总结了上述工作，并对未来工作进行了展望。