目錄
第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 目標函數為min-max 34
3.2.1 問題的有效多項式時間近似方案 34
3.2.2 問題的全多項式時間近似方案 39
3.3 目標函數為max-min 43
3.3.1 問題的多項式時間近似方案 43
3.3.2 問題的全多項式時間近似方案 50
3.3.3 問題的有效多項式時間近似方案 52
3.4 目標函數為 54
3.4.1 問題的2-近似算法 54
3.4.2 問題的全多項式時間近似方案 56
第4章 帶數目約束的負載均衡問題 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 目標函數為min-max 72
5.2.1 k為固定常數時的有效多項式時間近似方案 72
5.2.2 m為固定常數時的全多項式時間近似方案 74
5.3 目標函數為max-min 76
5.3.1 一般情形時的近似算法 76
5.3.2 k為固定常數時的有效多項式時間近似方案 77
5.3.3 m為固定常數時的全多項式時間近似方案 80
5.4 目標函數為min-lp 81
5.4.1 一般情形時的全范數2-近似算法 81
5.4.2 為固定常數時的全多項式時間近似方案 82
第6章 總結和展望 84
參考文獻 86