●章 緒言
1.1 研究背景
1.2 基本知識
1.3 主要內容
第2章 帶懲罰費用約束的負載均衡問題
2.1 引言
……
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章 總結和展望
參考文獻
內容簡介
負載均衡問題是組合優化領域早被研究的問題之一，也是目前受關注的問題之一。搶先發售近似比的概念正是在研究負載均衡的問題中提出來的。負載均衡問題在網絡設計、資源分配、工業管理、信息傳播與車輛調度中有著很好廣泛的應用，其目標函數通常有三類：小化大負載、大化小負載和小化負載向量的Zp範數。在這三個優化目標下，經典的平行機環境下負載均衡問題的研究較多，並且多數問題已經被接近解決。
《若干負載均衡問題的算法設計與分析》重點研究帶懲罰費用約束、帶等級約束、帶數目約束和帶劃分擬陣約束等四類不同約束下的負載均衡問題。在三個不同的優化目標下，深入地分析問題的計算復雜性，設計多項式時間算法，並分析算法的近似比。
《若干負載均衡問題的算法設計與分析》適用於運籌學、計算機科學或管理科學專業的研究生或從事組合優化研究的人員閱讀。
