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

本书特色

[

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

]

内容简介

[

负载平衡问题是组合很优化领域很受关注的问题之一.它在网络设计、资源分配、工业管理、信息传播与车辆调度中有着很好广泛的应用.其目标函数通常有三类:很小化优选负载、优选化很小负载和很小化负载向量的lp-范数.在上述三个优化目标下，经典的平行机排序问题的研究较多，大量相关问题都已经被解决。本书四类带不同类型约束(如带惩罚费用约束、带等级约束、带数目约束和带划分拟阵约束)的负载均衡问题，在三个优化目标下进行了广泛的研究，分析其计算复杂性，并设计了多个多项式时间近似算法，得到了一系列重要的结果。

]

目录

目录第1章 绪言 11.1 研究背景 11.2 基本知识 31.3 主要内容 5第2章 带惩罚费用约束的负载均衡问题 72.1 引言 72.2 问题的强多项式时间算法 102.3 辅助实例 152.4 近似方案 242.5 问题的全多项式时间近似方案 282.6 小结 30第3章 带等级约束的负载均衡问题 313.1 引言 313.2 目标函数为min-max 343.2.1 问题的有效多项式时间近似方案 343.2.2 问题的全多项式时间近似方案 393.3 目标函数为max-min 433.3.1 问题的多项式时间近似方案 433.3.2 问题的全多项式时间近似方案 503.3.3 问题的有效多项式时间近似方案 523.4 目标函数为 543.4.1 问题的2-近似算法 543.4.2 问题的全多项式时间近似方案 56第4章 带数目约束的负载均衡问题 604.1 引言 604.2 min-max CCLB问题的2-近似算法 614.3 max-min CCLB问题的1/2-1/3近似算法 644.4 min-lp CCLB问题的21-1/p-近似算法 65第5章 带划分拟阵约束的负载均衡问题 715.1 引言 715.2 目标函数为min-max 725.2.1 k为固定常数时的有效多项式时间近似方案 725.2.2 m为固定常数时的全多项式时间近似方案 745.3 目标函数为max-min 765.3.1 一般情形时的近似算法 765.3.2 k为固定常数时的有效多项式时间近似方案 775.3.3 m为固定常数时的全多项式时间近似方案 805.4 目标函数为min-lp 815.4.1 一般情形时的全范数2-近似算法 815.4.2 为固定常数时的全多项式时间近似方案 82第6章 总结和展望 84参考文献 86

封面

书名:若干负载均衡问题的算法设计与分析

作者:李伟东，李建平

页数:96

定价:¥59.0

出版社:科学出版社

出版日期:2019-10-01

ISBN:9787030625007

PDF电子书大小:40MB 高清扫描完整版