负载均衡问题是组合最优化领域最早被研究的问题之一，也是目前最受关注的问题之一。第一个近似比的概念正是在研究负载均衡的问题中提出来的。负载均衡问题在网络设计、资源分配、工业管理、信息传播与车辆调度中有着非常广泛的应用，其目标函数通常有三类：最小化最大负载、最大化最小负载和最小化负载向量的Zp范数。在这三个优化目标下，经典的平行机环境下负载均衡问题的研究较多，并且多数问题已经被完全解决。本书重点研究带惩罚费用约束、带等级约束、带数目约束和带划分拟阵约束等四类不同约束下的负载均衡问题。在三个不同的优化目标下，深入地分析问题的计算复杂性，设计多项式时间算法，并分析算法的近似比。
本书适用于运筹学、计算机科学或管理科学专业的研究生或从事组合最优化研究的人员阅读。

第1章 绪言
1.1 研究背景
1.2 基本知识
1.3 主要内容
第2章 带惩罚费用约束的负载均衡问题
2.1 引言
2.2 问题□（数理化公式）的强多项式时间算法
2.3 辅助实例
2.4 近似方案
2.5 问题□（数理化公式）的全多项式时间近似方案
2.6 小结
第3章 带等级约束的负载均衡问题
3.1 引言
3.2 目标函数为min-max
3.2.1 问题P|GoS2|Cmax的有效多项式时间近似方案
3.2.2 问题Pm|GoS|Cmax的全多项式时间近似方案
3.3 目标函数为max-min
3.3.1 问题P|GoS|Cmin的多项式时间近似方案
3.3.2 问题Pm|GoS|Cmin的全多项式时间近似方案
3.3.3 问题P|GoSk|Cmin的有效多项式时间近似方案
3.4 目标函数为min-lp
3.4.1 问题P|GoS|lp的2-近似算法
3.4.2 问题Pm|GoS|lp的全多项式时间近似方案
第4章 带数目约束的负载均衡问题
4.1 引言
4.2 min-max CCLB问题的2-近似算法
4.3 max-min CCLB问题的1/2-1/3近似算法
4.4 min-lp CCLB问题的21-1/p-近似算法
第5章 带划分拟阵约束的负载均衡问题
5.1 引言
5.2 目标函数为min-max
5.2.1 k为固定常数时的有效多项式时间近似方案
5.2.2 m为固定常数时的全多项式时间近似方案
5.3 目标函数为max-min
5.3.1 一般情形时的1/k-1-近似算法
5.3.2 k为固定常数时的有效多项式时间近似方案
5.3.3 m为固定常数时的全多项式时间近似方案
5.4 目标函数为min-lp
5.4.1 一般情形时的全范数2-近似算法
5.4.2 m为固定常数时的全多项式时间近似方案
第6章 总结和展望
参考文献