组合最优化 : 算法和复杂性

前言 i
第一章 最优化问题 1
1.1 引言 1
1.2 最优化问题 4
1.3 领域 8
1.4 局部最优与整体最优 10
· · · · · · (更多)

前言 i
第一章 最优化问题 1
1.1 引言 1
1.2 最优化问题 4
1.3 领域 8
1.4 局部最优与整体最优 10
1.5 凸集与凸函数 12
1.6 凸规划问题 15
习题 17
注释与参考资料 20
附录：术语与符号 21
A.1 线性代数 21
A.2 图论 22
A3 拟Algol语言 27
第二章 单纯形算法 30
2.1 线性规划问题的形式 30
2.2 基本可行解 33
2.3 线性规划的几何 39
2.3.1 线性空间和仿射空间 39
2.3.2 有界凸多面体 40
2.3.3 有界多面体与LP 43
2.4 基本可行解的替换 49
2.5 单纯形表 53
2.6 进入基列的选择 55
2.7 旋转元的选择和Bland反循环算法 61
2.8 单纯形算法的初始基本可行解 68
2.9 旋转变换的几何说明 73
习题 79
注释与参考资料 82
第三章 对偶性 86
3.1 一般形式的线性规划的对偶 86
3.2 互补松弛性 91
3.3 Farkas引理 93
3.4 最短路问题及其对偶 95
3.5 单纯形表中对偶解的信息 100
3.6 对偶单纯形算法 102
3.7 对偶单纯形算法的解释 104
习题 106
注释与参考资料 110
第四章 关于单纯形算法的计算讨论 112
4.1 修正的单纯形算法 112
4.2 修正的单纯形算法在计算上的意义 114
4.3 最大流问题及用修正的单纯形方法求其解 116
4.4 Dantzig-Wolfe的分解算法 122
习题 129
注释与参考资料 131
第五章 原始-对偶算法 132
5.1 引言 132
5.2 原始-对偶算法 133
5.3 原始-对偶算法的说明 137
5.4 最短路问题的原始-对偶算法 138
5.5 关于方法思路的说明 143
5.6 最大流问题的原始-对偶算法 144
习题 146
注释与参考资料 147
第六章 最大流和最短路的原始-对偶算法：Ford-Fulkerson算法和Dijkstra算法 148
6.1 最大流最小截定理 148
6.2 Ford和Fulkerson标号算法 152
6.3 标号算法的有限性问题 156
6.4 Dijkstra算法 161
6.5 Floyd-Warshall算法 163
习题 167
注释与参考资料 170
第七章 最小费用流的原始-对偶算法 172
7.1 最小费用流问题 172
7.2 组合化容量-圈算法 173
7.3 组合化费用-迭加算法 177
7.4 Hitchcock问题的原始-对偶算法-αβ算法 179
7.5 最小费用流问题变换为Hitchcock问题 185
7.6 结束语 189
习题 190
注释与参考资料 192
第八章 算法与复杂性 198
8.1 可计算性 198
8.2 时间界 199
8.3 例子的规模 202
8.4 算法分析 206
8.5 多项式时间算法 207
8.6 单纯形算法不是多项式时间的算法 210
8.7 椭球算法 216
8.7.1 LP, LI和LSI 216
8.7.2 仿射变换与椭球 221
8.7.3 算法 223
8.7.4 算法的精度 230
习题 235
注释与参考资料 241
第九章 最大流问题的有效算法 248
9.1 图的搜索 248
9.2 标号算法的病症是什么 254
9.3 网络标号与有向图的搜索 258
9.4 一个O(|V|^3)的最大流算法 263
9.5 具有单位容量的情况 269
习题 272
注释与参考资料 275
第十章 匹配算法 279
10.1 匹配问题 279
10.2 二部图的匹配算法 283
10.3 二部图匹配与网络流 287
10.4 非二部图的匹配：花 289
10.5 非二部图匹配：一个算法 298
习题 309
注释与参考资料 313
第十一章 赋权匹配 316
11.1 引言 316
11.2 指派问题的匈牙利方法 317
11.3 非二部图赋权匹配问题 326
11.4 小结 341
习题 342
注释与参考资料 346
第十二章 支撑树与拟阵 348
12.1 最小支撑树问题 348
12.2 最小支撑树问题的O(|E|log|V|)算法 352
12.3 Greedy算法 356
12.4 拟阵 358
12.5 两个拟阵的交 369
12.6 拟阵交问题的某些推广 381
12.6.1 赋权拟阵交 381
12.6.2 拟阵对 382
12.6.3 三个拟阵交 383
习题 385
注释与参考资料 391
第十三章 整数线性规划 395
13.1 引言 395
13.2 全单位模性质 406
13.3 ILP解的上界 409
习题 416
注释与参考资料 417
第十四章 整数线性规划的割平面算法 420
14.1 Gomory割 420
14.2 字典序 429
14.3 分数对偶算法的有限性 434
14.4 其它的割平面算法 436
习题 437
注释与参考资料 439
第十五章 NP-完备问题 441
15.1 引言 441
15.2 一个最优化问题的三种提法 442
15.3 P类与NP类 447
15.4 多项式时间的归结 452
15.5 Cook定理 454
15.6 几个NP-完备问题：团与货郎问题 461
15.7 另一些NP-完备问题：匹配、覆盖和划分 476
习题 483
注释与参考资料 488
第十六章 再论NP-完备性 493
16.1 co-NP类 493
16.2 拟多项式算法和“强”NP-完备性 497
16.3 NP-完备问题的特例和一般化 502
16.3.1 使用限制方法证明NP-完备性 503
16.3.2 NP-完备问题的容易特例 504
16.3.3 NP-完备问题的困难特例 506
16.4 一些有关的概念 509
16.4.1 多项式时间约化 509
16.4.2 NP困难问题 509
16.4.3 非确定的图灵机 511
16.4.4 多项式空间完备问题 513
16.5 结束语 514
习题 515
注释与参考资料 519
第十七章 近似算法 523
17.1 点覆盖的启发式方法：一个例子 523
17.2 货郎问题的近似算法 527
17.3 近似方法 539
17.4 一些否定的结果 549
习题 554
注释与参考资料 555
第十八章 分枝定界和动态规划 559
18.1 整数线性规划的分枝定界 559
18.2 一般意义下的分枝定界 564
18.3 优势关系 570
18.4 分枝定界策略 571
18.5 应用于流水作业车间时间表问题 573
18.6 动态规划 578
习题 581
注释与参考资料 583
第十九章 局部寻优法 586
19.1 引言 586
19.2 问题1：货郎问题 587
19.3 问题2：最小费用残存网络 589
19.4 问题3：海底天然气管道系统拓朴结构 595
19.5 问题4：均匀图划分 599
19.6 局部寻优法的一些普遍性问题 604
19.7 局部寻优法的几何 608
19.8 一个大的极小精确领域的例子 613
19.9 货郎问题的精确局部寻优法的复杂性 616
习题 621
注释与参考资料 624
· · · · · · (收起)