若干负载均衡问题的算法设计与分析 pdf下载

供从事近似算法研究的学者、研究生阅读

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

　　排序与调度是运筹学领域最为活跃的分支之一，是管理科学与工程、计算机科学与技术、运筹学和控制科学与工程等学科的一个重要研究方向。历经数十年的发展，形成了精确算法、近似算法、参数算法和智能算法等各种算法工具百花齐放的局面，为生产生活的相关领域提供了重要的理论支撑和技术支持。
　　负载均衡问题作为排序与调度领域最为经典的问题之一，其研究成果丰富，理论理解深刻，受到数学专业相关研究人员的极大关注。近似比刻画了算法在最坏情形下所求得的解的质量，不依赖于数据输入，从理论上保证了算法的性能。本书以三种不同目标函数下四类不同的负载均衡问题为研究内容，贯穿计算复杂性理论和近似比分析的主线，介绍采用动态规划、数学规划和图算法等多种工具设计算法的技巧，为从事近似算法研究的研究生或教师提供参考。
　　本书是作者在负载均衡领域最近几年研究成果的基础上系统整理后形成的。由云南大学数学与统计学院李建平教授（云南省“万人计划”云岭学者）和李伟东副教授（云南省“万人计划”青年拔尖人才）共同撰写而成。本书的出版受到国家自然科学基金（11301466）、云南大学青年英才培育计划、云南大学运筹学省创新团队（培育）、云南省高校科技创新团队支持计划和云南大学双一流数学学科建设项目等多个项目的资助，在此特别感谢各个资助单位。由于作者水平有限，书中难免有疏漏之处，敬请批评指正。