若干負(fù)載均衡問題的算法設(shè)計與分析
負(fù)載均衡問題是組合**化領(lǐng)域*早被研究的問題之一，也是目前*受關(guān)注的問題之一。**個近似比的概念正是在研究負(fù)載均衡的問題中提出來的。負(fù)載均衡問題在網(wǎng)絡(luò)設(shè)計、資源分配、工業(yè)管理、信息傳播與車輛調(diào)度中有著非常廣泛的應(yīng)用，其目標(biāo)函數(shù)通常有三類: *小化**負(fù)載、**化*小負(fù)載和*小化負(fù)載向量的lp范數(shù)。在這三個優(yōu)化目標(biāo)下，經(jīng)典的平行機(jī)環(huán)境下負(fù)載均衡問題的研究較多，并且多數(shù)問題已經(jīng)被完全解決。《若干負(fù)載均衡問題的算法設(shè)計與分析》重點(diǎn)研究帶懲罰費(fèi)用約束、帶等級約束、帶數(shù)目約束和帶劃分?jǐn)M陣約束等四類不同約束下的負(fù)載均衡問題。在三個不同的優(yōu)化目標(biāo)下，深入地分析問題的計算復(fù)雜性，設(shè)計多項(xiàng)式時間算法，并分析算法的近似比。
更多科學(xué)出版社服務(wù)，請掃碼獲取。
算法設(shè)計,算法分析
目錄
第1章 緒言 1
1.1 研究背景 1
1.2 基本知識 3
1.3 主要內(nèi)容 5
第2章 帶懲罰費(fèi)用約束的負(fù)載均衡問題 7
2.1 引言 7
2.2 問題的強(qiáng)多項(xiàng)式時間算法 10
2.3 輔助實(shí)例 15
2.4 近似方案 24
2.5 問題的全多項(xiàng)式時間近似方案 28
2.6 小結(jié) 30
第3章 帶等級約束的負(fù)載均衡問題 31
3.1 引言 31
3.2 目標(biāo)函數(shù)為min-max 34
3.2.1 問題的有效多項(xiàng)式時間近似方案 34
3.2.2 問題的全多項(xiàng)式時間近似方案 39
3.3 目標(biāo)函數(shù)為max-min 43
3.3.1 問題的多項(xiàng)式時間近似方案 43
3.3.2 問題的全多項(xiàng)式時間近似方案 50
3.3.3 問題的有效多項(xiàng)式時間近似方案 52
3.4 目標(biāo)函數(shù)為 54
3.4.1 問題的2-近似算法 54
3.4.2 問題的全多項(xiàng)式時間近似方案 56
第4章 帶數(shù)目約束的負(fù)載均衡問題 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章 帶劃分?jǐn)M陣約束的負(fù)載均衡問題 71
5.1 引言 71
5.2 目標(biāo)函數(shù)為min-max 72
5.2.1 k為固定常數(shù)時的有效多項(xiàng)式時間近似方案 72
5.2.2 m為固定常數(shù)時的全多項(xiàng)式時間近似方案 74
5.3 目標(biāo)函數(shù)為max-min 76
5.3.1 一般情形時的近似算法 76
5.3.2 k為固定常數(shù)時的有效多項(xiàng)式時間近似方案 77
5.3.3 m為固定常數(shù)時的全多項(xiàng)式時間近似方案 80
5.4 目標(biāo)函數(shù)為min-lp 81
5.4.1 一般情形時的全范數(shù)2-近似算法 81
5.4.2 為固定常數(shù)時的全多項(xiàng)式時間近似方案 82
第6章 總結(jié)和展望 84
參考文獻(xiàn) 86
書單推薦
