若干負載均衡問題的算法設計與分析

定　價：￥59.00

作　者：	李偉東，李建平
出版社：	科學出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

ISBN：	9787030625007	出版時間：	2019-10-01	包裝：
開本：	16開	頁數(shù)：	96	字數(shù)：

內容簡介

　　負載平衡問題是組合*優(yōu)化領域*受關注的問題之一.它在網(wǎng)絡設計、資源分配、工業(yè)管理、信息傳播與車輛調度中有著非常廣泛的應用.其目標函數(shù)通常有三類：*小化*大負載、*大化*小負載和*小化負載向量的lp-范數(shù).在上述三個優(yōu)化目標下，經典的平行機排序問題的研究較多，大量相關問題都已經被解決。本書四類帶不同類型約束（如帶懲罰費用約束、帶等級約束、帶數(shù)目約束和帶劃分擬陣約束）的負載均衡問題，在三個優(yōu)化目標下進行了廣泛的研究，分析其計算復雜性，并設計了多個多項式時間近似算法，得到了一系列重要的結果。

作者簡介

暫缺《若干負載均衡問題的算法設計與分析》作者簡介

圖書目錄

目錄
第1章緒言 1
1.1 研究背景 1
1.2 基本知識 3
1.3 主要內容 5
第2章帶懲罰費用約束的負載均衡問題 7
2.1 引言 7
2.2 問題的強多項式時間算法 10
2.3 輔助實例 15
2.4 近似方案 24
2.5 問題的全多項式時間近似方案 28
2.6 小結 30
第3章帶等級約束的負載均衡問題 31
3.1 引言 31
3.2 目標函數(shù)為min-max 34
3.2.1 問題的有效多項式時間近似方案 34
3.2.2 問題的全多項式時間近似方案 39
3.3 目標函數(shù)為max-min 43
3.3.1 問題的多項式時間近似方案 43
3.3.2 問題的全多項式時間近似方案 50
3.3.3 問題的有效多項式時間近似方案 52
3.4 目標函數(shù)為 54
3.4.1 問題的2-近似算法 54
3.4.2 問題的全多項式時間近似方案 56
第4章帶數(shù)目約束的負載均衡問題 60
4.1 引言 60
4.2 min-max CCLB問題的2-近似算法 61
4.3 max-min CCLB問題的1/2-1/3近似算法 64
4.4 min-lp CCLB問題的21-1/p-近似算法 65
第5章帶劃分擬陣約束的負載均衡問題 71
5.1 引言 71
5.2 目標函數(shù)為min-max 72
5.2.1 k為固定常數(shù)時的有效多項式時間近似方案 72
5.2.2 m為固定常數(shù)時的全多項式時間近似方案 74
5.3 目標函數(shù)為max-min 76
5.3.1 一般情形時的近似算法 76
5.3.2 k為固定常數(shù)時的有效多項式時間近似方案 77
5.3.3 m為固定常數(shù)時的全多項式時間近似方案 80
5.4 目標函數(shù)為min-lp 81
5.4.1 一般情形時的全范數(shù)2-近似算法 81
5.4.2 為固定常數(shù)時的全多項式時間近似方案 82
第6章總結和展望 84
參考文獻 86