定 價(jià)：148 元
叢書名：現(xiàn)代數(shù)學(xué)譯叢;23
- 作者：(德)科泰(Korte，B.)等著
- 出版時(shí)間：2014/1/1
- ISBN：9787030393425
- 出 版 社：科學(xué)出版社
- 中圖法分類：O122.4
- 頁(yè)碼：541頁(yè)
- 紙張：膠版紙
- 版次：1
- 開本：16K
《組合最優(yōu)化：理論與算法》系統(tǒng)和全面地介紹了組合優(yōu)化的基本理論和重要算法. 《組合優(yōu)化：理論與算法》共分22 章, 內(nèi)容既包括圖論、線性和整數(shù)規(guī)劃以及計(jì)算復(fù)雜性等基礎(chǔ)部分, 又涵蓋了組合優(yōu)化中若干重要問(wèn)題的經(jīng)典結(jié)果和最新進(jìn)展. 除了對(duì)理論的深刻討論外, 書中還提供了豐富的研究文獻(xiàn)和具有挑戰(zhàn)性的習(xí)題.
更多科學(xué)出版社服務(wù)，請(qǐng)掃碼獲取。
該書是原書作者在2005年英文版第三版的基礎(chǔ)上，進(jìn)一步修訂后，由越民義等4位中國(guó)數(shù)學(xué)家翻譯為中文版。該書范內(nèi)容全面，取材得當(dāng)，適于教學(xué)之用。中譯本的出版，對(duì)推動(dòng)組合優(yōu)化這門學(xué)科在我國(guó)之發(fā)展，也將起到重要的推動(dòng)作用。
該書是原書作者在2005年英文版第三版的基礎(chǔ)上，進(jìn)一步修訂后，由越民義等4位中國(guó)數(shù)學(xué)家翻譯為中文版。該書范內(nèi)容全面，取材得當(dāng)，適于教學(xué)之用。中譯本的出版，對(duì)推動(dòng)組合優(yōu)化這門學(xué)科在我國(guó)之發(fā)展，也將起到重要的推動(dòng)作用。<br />
該書作者Korte是國(guó)際著名優(yōu)化專家；譯者越民義等，越民義，著名數(shù)學(xué)家。我國(guó)運(yùn)籌學(xué)研究的先驅(qū)之一和學(xué)術(shù)帶頭人。在排隊(duì)論、非線性最優(yōu)化和組合優(yōu)化方面取得了多項(xiàng)國(guó)際領(lǐng)先水平的重要研究成果。
目錄
譯者序
第四版序言
第三版序言
第二版序言
第一版序言
符號(hào)表
第1章 引言 1
1.1 枚舉法 2
1.2 算法的運(yùn)行時(shí)間 4
1.3 線性優(yōu)化問(wèn)題 7
1.4 整序 8
習(xí)題 10
參考文獻(xiàn) 10
第2章 圖 12
2.1 基本定義 12
2.2 樹，圈和截 15
2.3 連通性 22
2.4 歐拉圖和二部圖 27
2.5 可平面性 30
2.6 平面對(duì)偶性 36
習(xí)題 38
參考文獻(xiàn) 41
第3章 線性規(guī)劃 43
3.1 多面體 44
3.2 單純形法 47
3.3 單純形法的執(zhí)行 50
3.4 對(duì)偶性 53
3.5 凸包和多面體 57
習(xí)題 58
參考文獻(xiàn) 60
第4章 線性規(guī)劃算法 62
4.1 頂點(diǎn)和面的尺寸 62
4.2 連分?jǐn)?shù) 64
4.3 高斯消去法 67
4.4 橢球法 70
4.5 Khachiyan定理 76
4.6 分離和優(yōu)化 77
習(xí)題 83
參考文獻(xiàn) 84
第5章 整數(shù)規(guī)劃 86
5.1 多胞形的整數(shù)閉包 87
5.2 單模變換 91
5.3 全對(duì)偶整性 93
5.4 全單模矩陣 96
5.5 割平面 100
5.6 拉格朗日松弛 104
習(xí)題 106
參考文獻(xiàn) 109
第6章 支撐樹和樹形圖 111
6.1 最小支撐樹 111
6.2 最小樹形圖 116
6.3 多面體描述 119
6.4 儲(chǔ)存支撐樹和樹形圖 122
習(xí)題 125
參考文獻(xiàn) 128
第7章 最短路 131
7.1 一個(gè)起點(diǎn)的最短路 132
7.2 全部點(diǎn)對(duì)間的最短路 136
7.3 最小平均圈 138
習(xí)題 140
參考文獻(xiàn) 141
第8章 網(wǎng)絡(luò)流 144
8.1 最大流-最小截定理 145
8.2 Menger定理 148
8.3 Edmonds-Karp算法 150
8.4 阻塞流與Fujishige算法 152
8.5 Goldberg-Tarjan算法 154
8.6 Gomory-Hu樹 158
8.7 無(wú)向圖的最小容量截 164
習(xí)題 166
參考文獻(xiàn) 169
第9章 最小費(fèi)用流 174
9.1 問(wèn)題表述 174
9.2 最優(yōu)性準(zhǔn)則 176
9.3 最小平均圈消去算法 178
9.4 逐次最短路算法 181
9.5 Orlin算法 185
9.6 網(wǎng)絡(luò)單形算法 188
9.7 時(shí)變流 192
習(xí)題 193
參考文獻(xiàn) 196
第10章 最大匹配 199
10.1 二部圖匹配 199
10.2 Tutte矩陣 201
10.3 Tutte定理 203
10.4 因子臨界圖的耳分解 206
10.5 Edmonds匹配算法 210
習(xí)題 219
參考文獻(xiàn) 222
第11章 加權(quán)匹配 225
11.1 分配問(wèn)題 225
11.2 加權(quán)匹配算法概述 227
11.3 加權(quán)匹配算法的實(shí)現(xiàn) 229
11.4 后續(xù)優(yōu)化 241
11.5 匹配多面體 242
習(xí)題 245
參考文獻(xiàn) 246
第12章 b-匹配與T-連接 249
12.1 b-匹配 249
12.2 最小權(quán)T-連接 252
12.3 T-連接與T-截 256
12.4 Padberg-Rao定理 259
習(xí)題 261
參考文獻(xiàn) 263
第13章 擬陣 265
13.1 獨(dú)立系統(tǒng)與擬陣 265
13.2 另外的擬陣公理 268
13.3 對(duì)偶 273
13.4 貪婪算法 276
13.5 擬陣交 281
13.6 擬陣劃分 285
13 7 加權(quán)擬陣交 286
習(xí)題 290
參考文獻(xiàn) 292
第14章 擬陣的推廣 294
14.1 廣義擬陣 294
14.2 擬陣多面體 297
14.3 求次模函數(shù)的最小值 301
14.4 Schrijver算法 303
14.5 對(duì)稱次模函數(shù) 307
習(xí)題 309
參考文獻(xiàn) 310
第15章 NP完備性 313
15.1 Turing機(jī) 313
15.2 Church的論題 315
15.3 P與NP 320
15.4 Cook定理 324
15.5 某些基本的NP完備問(wèn)題 328
15.6 coNP類 334
15 7 NP難問(wèn)題 336
習(xí)題 339
參考文獻(xiàn) 342
第16章 近似算法 344
16.1 集覆蓋 344
16.2 Max-Cut（最大割）問(wèn)題 349
16.3 著色 355
16.4 近似方案 361
16.5 最大可滿足性 364
16.6 PCP定理 368
16.7 L歸約 372
習(xí)題 378
參考文獻(xiàn) 380
第17章 背包問(wèn)題 386
17.1 分?jǐn)?shù)型背包問(wèn)題和賦權(quán)中位問(wèn)題 386
17.2 偽多項(xiàng)式算法 388
17.3 一個(gè)全多項(xiàng)式近似方案 390
習(xí)題 393
參考文獻(xiàn) 393
第18章 裝箱問(wèn)題 395
18.1 貪婪算法 395
18.2 漸近近似方案 400
18.3 Karmarkar-Karp算法 404
習(xí)題 407
參考文獻(xiàn) 408
第19章 多商品流和邊不重路 410
19.1 多商品流 411
19.2 多商品流算法 414
19.3 有向的邊不重路問(wèn)題 418
19.4 無(wú)向的邊不重路問(wèn)題 421
習(xí)題 426
參考文獻(xiàn) 427
第20章 網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題 431
20.1 Steiner樹 431
20.2 Robins-Zelikovsky算法 436
20.3 可靠網(wǎng)絡(luò)設(shè)計(jì) 441
20.4 原始對(duì)偶近似算法 444
20.5 Jain算法 452
刁題 457
參考文獻(xiàn) 459
第21章 旅行商問(wèn)題 463
21.1 旅行商問(wèn)題的近似算法 463
21.2 歐氏平面上的旅行商問(wèn)題 467
21.3 局部搜索 474
21.4 旅行商多面體 479
21.5 下界 484
21.6 分枝定界 487
習(xí)題 489
參考文獻(xiàn) 491
第22章 選址問(wèn)題 495
22.1 無(wú)容量限制的設(shè)施選址問(wèn)題 495
22.2 基于線性規(guī)劃的舍入算法 497
22.3 原始對(duì)偶算法 499
22.4 放縮與貪婪增廣方法 504
22.5 界定設(shè)施的數(shù)目 507
22.6 局部搜索 510
22.7 有容量限制的設(shè)施選址問(wèn)題 515
22.8 設(shè)施選址問(wèn)題的一般模型 518
習(xí)題 524
參考文獻(xiàn) 525
名詞索引 528
《現(xiàn)代數(shù)學(xué)譯叢》已出版書目 543
符號(hào)表
自然數(shù)集
{1, 2, 3, ···}
(非負(fù))整數(shù)集(非負(fù))有理數(shù)集(非負(fù))實(shí)數(shù)集真子集子集不交并集合X與Y的對(duì)稱差向量x的歐氏范數(shù)向量x的無(wú)窮范數(shù)唯一數(shù)z使得0.z
x.z
向量x與矩陣A的轉(zhuǎn)置不嚴(yán)格小于x的最小整數(shù)不嚴(yán)格大于x的最大整數(shù)O表示法Θ表示法x的編碼長(zhǎng)度;x的二進(jìn)制字符串長(zhǎng)度x以2為底的對(duì)數(shù)圖G的頂點(diǎn)集圖G的邊集由X. V(G)誘導(dǎo)的G的子圖圖G中由V(G)\{v} 誘導(dǎo)的子圖圖G刪去邊e的子圖圖G添加邊e后的圖圖G和H的并集在圖G中將頂點(diǎn)集X收縮成單點(diǎn)所得的生成圖兩端點(diǎn)分別在頂點(diǎn)集X\ Y 和Y \ X 的邊集頂點(diǎn)集X \ Y 到Y(jié) \ X的有向邊集E(X,V(G)\ X),E({v},V(G)\{v})頂點(diǎn)集X的鄰點(diǎn)集,頂點(diǎn)v的鄰點(diǎn)集頂點(diǎn)集X的出邊集,頂點(diǎn)v的出邊集頂點(diǎn)集X的入邊集,頂點(diǎn)v的入邊集S的冪集
Kn
P[x,y]dist(v,w)
c(F)
Kn,m
cr(J,l)
G.
e.
T
xy,xyx.yrank(A)dimXI
ej
AJ
bJ
1l
AJ
conv(X)detAsgn(π)E(A,x)B(x,r)volume(X)
||A||
X.PIΞ(A)P., P (i)
LR(λ)
δ(X1,,Xp)
···
cπ((x,y))
(ˉ c)
G, ˉ
exf(v)
value(f)
.
G
←
e
n個(gè)頂點(diǎn)的完全圖路徑P的x-y子路徑最短v-w路徑的長(zhǎng)度.c(e)(假設(shè)c:ER以及F. E)
→
e∈F
n個(gè)和m個(gè)頂點(diǎn)構(gòu)成的完全二分圖多胞形J與直線l的交點(diǎn)數(shù)圖G的平面對(duì)偶圖圖G. 的一條邊;邊e的對(duì)偶向量x與y的內(nèi)積給定向量x和y,不等號(hào)在x和y的每個(gè)分量上成立矩陣A的秩非空集X. Rn 的維數(shù)單位陣j-單位向量(第j個(gè)分量為1,其余為0)由矩陣A中J的對(duì)應(yīng)行組成的子矩陣由向量b中指標(biāo)集J對(duì)應(yīng)元素組成的子向量各分量均為1的向量由矩陣A中指標(biāo)集J所對(duì)應(yīng)列組成的子矩陣集合X中所有向量的凸包矩陣A的行列式排列π的符號(hào)函數(shù)橢球歐氏空間中以x為圓心、r為半徑的球非空集X. Rn 的容積矩陣A的范數(shù)集合X的極點(diǎn)集多胞形P的整數(shù)包矩陣A子行列式的最大絕對(duì)值P的1階,i階Gomory-Chv′atal割體拉格朗日松弛多割邊(x,y)關(guān)于π所降低的費(fèi)用(G,c)在度量空間中的閉包頂點(diǎn)v的入流
書單推薦
