目錄
譯者序
第四版序言
第三版序言
第二版序言
第一版序言
符號表
第1章 引言 1
1.1 枚舉法 2
1.2 算法的運行時間 4
1.3 線性優(yōu)化問題 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 平面對偶性 36
習(xí)題 38
參考文獻(xiàn) 41
第3章 線性規(guī)劃 43
3.1 多面體 44
3.2 單純形法 47
3.3 單純形法的執(zhí)行 50
3.4 對偶性 53
3.5 凸包和多面體 57
習(xí)題 58
參考文獻(xiàn) 60
第4章 線性規(guī)劃算法 62
4.1 頂點和面的尺寸 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 全對偶整性 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 儲存支撐樹和樹形圖 122
習(xí)題 125
參考文獻(xiàn) 128
第7章 最短路 131
7.1 一個起點的最短路 132
7.2 全部點對間的最短路 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 無向圖的最小容量截 164
習(xí)題 166
參考文獻(xiàn) 169
第9章 最小費用流 174
9.1 問題表述 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 時變流 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 分配問題 225
11.2 加權(quán)匹配算法概述 227
11.3 加權(quán)匹配算法的實現(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 獨立系統(tǒng)與擬陣 265
13.2 另外的擬陣公理 268
13.3 對偶 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 對稱次模函數(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完備問題 328
15.6 coNP類 334
15 7 NP難問題 336
習(xí)題 339
參考文獻(xiàn) 342
第16章 近似算法 344
16.1 集覆蓋 344
16.2 Max-Cut（最大割）問題 349
16.3 著色 355
16.4 近似方案 361
16.5 最大可滿足性 364
16.6 PCP定理 368
16.7 L歸約 372
習(xí)題 378
參考文獻(xiàn) 380
第17章 背包問題 386
17.1 分?jǐn)?shù)型背包問題和賦權(quán)中位問題 386
17.2 偽多項式算法 388
17.3 一個全多項式近似方案 390
習(xí)題 393
參考文獻(xiàn) 393
第18章 裝箱問題 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 有向的邊不重路問題 418
19.4 無向的邊不重路問題 421
習(xí)題 426
參考文獻(xiàn) 427
第20章 網(wǎng)絡(luò)設(shè)計問題 431
20.1 Steiner樹 431
20.2 Robins-Zelikovsky算法 436
20.3 可靠網(wǎng)絡(luò)設(shè)計 441
20.4 原始對偶近似算法 444
20.5 Jain算法 452
刁題 457
參考文獻(xiàn) 459
第21章 旅行商問題 463
21.1 旅行商問題的近似算法 463
21.2 歐氏平面上的旅行商問題 467
21.3 局部搜索 474
21.4 旅行商多面體 479
21.5 下界 484
21.6 分枝定界 487
習(xí)題 489
參考文獻(xiàn) 491
第22章 選址問題 495
22.1 無容量限制的設(shè)施選址問題 495
22.2 基于線性規(guī)劃的舍入算法 497
22.3 原始對偶算法 499
22.4 放縮與貪婪增廣方法 504
22.5 界定設(shè)施的數(shù)目 507
22.6 局部搜索 510
22.7 有容量限制的設(shè)施選址問題 515
22.8 設(shè)施選址問題的一般模型 518
習(xí)題 524
參考文獻(xiàn) 525
名詞索引 528
《現(xiàn)代數(shù)學(xué)譯叢》已出版書目 543