若干負(fù)載均衡問題的算法設(shè)計與分析

定　價：￥59.00

作　者：	李偉東，李建平
出版社：	科學(xué)出版社
叢編項：
標(biāo)　簽：	暫缺

購買這本書可以去

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

目錄
第1章緒言 1
1.1 研究背景 1
1.2 基本知識 3
1.3 主要內(nèi)容 5
第2章帶懲罰費用約束的負(fù)載均衡問題 7
2.1 引言 7
2.2 問題的強(qiáng)多項式時間算法 10
2.3 輔助實例 15
2.4 近似方案 24
2.5 問題的全多項式時間近似方案 28
2.6 小結(jié) 30
第3章帶等級約束的負(fù)載均衡問題 31
3.1 引言 31
3.2 目標(biāo)函數(shù)為min-max 34
3.2.1 問題的有效多項式時間近似方案 34
3.2.2 問題的全多項式時間近似方案 39
3.3 目標(biāo)函數(shù)為max-min 43
3.3.1 問題的多項式時間近似方案 43
3.3.2 問題的全多項式時間近似方案 50
3.3.3 問題的有效多項式時間近似方案 52
3.4 目標(biāo)函數(shù)為 54
3.4.1 問題的2-近似算法 54
3.4.2 問題的全多項式時間近似方案 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ù)時的有效多項式時間近似方案 72
5.2.2 m為固定常數(shù)時的全多項式時間近似方案 74
5.3 目標(biāo)函數(shù)為max-min 76
5.3.1 一般情形時的近似算法 76
5.3.2 k為固定常數(shù)時的有效多項式時間近似方案 77
5.3.3 m為固定常數(shù)時的全多項式時間近似方案 80
5.4 目標(biāo)函數(shù)為min-lp 81
5.4.1 一般情形時的全范數(shù)2-近似算法 81
5.4.2 為固定常數(shù)時的全多項式時間近似方案 82
第6章總結(jié)和展望 84
參考文獻(xiàn) 86