第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