本书系统和全面地介绍了组合优化的基本理论和重要算法。全书共分22章，内容既包括图论、线性和整数规划以及计算复杂性等基础部分，又涵盖了组合优化中若干重要问题的经典结果和最新进展．除了对理论的深刻讨论外，书中还提供了丰富的研究文献和具有挑战性的习题。
样章试读
目录
- 目录
译者序
第四版序言
第三版序言
第二版序言
第一版序言
符号表
第1章 引言 1
1.1 枚举法 2
1.2 算法的运行时间 4
1.3 线性优化问题 7
1.4 整序 8
习题 10
参考文献 10
第2章 图 12
2.1 基本定义 12
2.2 树，圈和截 15
2.3 连通性 22
2.4 欧拉图和二部图 27
2.5 可平面性 30
2.6 平面对偶性 36
习题 38
参考文献 41
第3章 线性规划 43
3.1 多面体 44
3.2 单纯形法 47
3.3 单纯形法的执行 50
3.4 对偶性 53
3.5 凸包和多面体 57
习题 58
参考文献 60
第4章 线性规划算法 62
4.1 顶点和面的尺寸 62
4.2 连分数 64
4.3 高斯消去法 67
4.4 椭球法 70
4.5 Khachiyan定理 76
4.6 分离和优化 77
习题 83
参考文献 84
第5章 整数规划 86
5.1 多胞形的整数闭包 87
5.2 单模变换 91
5.3 全对偶整性 93
5.4 全单模矩阵 96
5.5 割平面 100
5.6 拉格朗日松弛 104
习题 106
参考文献 109
第6章 支撑树和树形图 111
6.1 最小支撑树 111
6.2 最小树形图 116
6.3 多面体描述 119
6.4 储存支撑树和树形图 122
习题 125
参考文献 128
第7章 最短路 131
7.1 一个起点的最短路 132
7.2 全部点对间的最短路 136
7.3 最小平均圈 138
习题 140
参考文献 141
第8章 网络流 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
习题 166
参考文献 169
第9章 最小费用流 174
9.1 问题表述 174
9.2 最优性准则 176
9.3 最小平均圈消去算法 178
9.4 逐次最短路算法 181
9.5 Orlin算法 185
9.6 网络单形算法 188
9.7 时变流 192
习题 193
参考文献 196
第10章 最大匹配 199
10.1 二部图匹配 199
10.2 Tutte矩阵 201
10.3 Tutte定理 203
10.4 因子临界图的耳分解 206
10.5 Edmonds匹配算法 210
习题 219
参考文献 222
第11章 加权匹配 225
11.1 分配问题 225
11.2 加权匹配算法概述 227
11.3 加权匹配算法的实现 229
11.4 后续优化 241
11.5 匹配多面体 242
习题 245
参考文献 246
第12章 b-匹配与T-连接 249
12.1 b-匹配 249
12.2 最小权T-连接 252
12.3 T-连接与T-截 256
12.4 Padberg-Rao定理 259
习题 261
参考文献 263
第13章 拟阵 265
13.1 独立系统与拟阵 265
13.2 另外的拟阵公理 268
13.3 对偶 273
13.4 贪婪算法 276
13.5 拟阵交 281
13.6 拟阵划分 285
13 7 加权拟阵交 286
习题 290
参考文献 292
第14章 拟阵的推广 294
14.1 广义拟阵 294
14.2 拟阵多面体 297
14.3 求次模函数的最小值 301
14.4 Schrijver算法 303
14.5 对称次模函数 307
习题 309
参考文献 310
第15章 NP完备性 313
15.1 Turing机 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
习题 339
参考文献 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
习题 378
参考文献 380
第17章 背包问题 386
17.1 分数型背包问题和赋权中位问题 386
17.2 伪多项式算法 388
17.3 一个全多项式近似方案 390
习题 393
参考文献 393
第18章 装箱问题 395
18.1 贪婪算法 395
18.2 渐近近似方案 400
18.3 Karmarkar-Karp算法 404
习题 407
参考文献 408
第19章 多商品流和边不重路 410
19.1 多商品流 411
19.2 多商品流算法 414
19.3 有向的边不重路问题 418
19.4 无向的边不重路问题 421
习题 426
参考文献 427
第20章 网络设计问题 431
20.1 Steiner树 431
20.2 Robins-Zelikovsky算法 436
20.3 可靠网络设计 441
20.4 原始对偶近似算法 444
20.5 Jain算法 452
刁题 457
参考文献 459
第21章 旅行商问题 463
21.1 旅行商问题的近似算法 463
21.2 欧氏平面上的旅行商问题 467
21.3 局部搜索 474
21.4 旅行商多面体 479
21.5 下界 484
21.6 分枝定界 487
习题 489
参考文献 491
第22章 选址问题 495
22.1 无容量限制的设施选址问题 495
22.2 基于线性规划的舍入算法 497
22.3 原始对偶算法 499
22.4 放缩与贪婪增广方法 504
22.5 界定设施的数目 507
22.6 局部搜索 510
22.7 有容量限制的设施选址问题 515
22.8 设施选址问题的一般模型 518
习题 524
参考文献 525
名词索引 528
《现代数学译丛》已出版书目 543
京公网安备 11010102004214号