《组合最优化：理论与算法》系统和全面地介绍了组合优化的基本理论和重要算法. 《组合优化：理论与算法》共分22 章, 内容既包括图论、线性和整数规划以及计算复杂性等基础部分, 又涵盖了组合优化中若干重要问题的经典结果和最新进展. 除了对理论的深刻讨论外, 书中还提供了丰富的研究文献和具有挑战性的习题.
更多科学出版社服务，请扫码获取。
该书是原书作者在2005年英文版第三版的基础上，进一步修订后，由越民义等4位中国数学家翻译为中文版。该书范内容全面，取材得当，适于教学之用。中译本的出版，对推动组合优化这门学科在我国之发展，也将起到重要的推动作用。
该书是原书作者在2005年英文版第三版的基础上，进一步修订后，由越民义等4位中国数学家翻译为中文版。该书范内容全面，取材得当，适于教学之用。中译本的出版，对推动组合优化这门学科在我国之发展，也将起到重要的推动作用。<br />
该书作者Korte是国际著名优化专家；译者越民义等，越民义，著名数学家。我国运筹学研究的先驱之一和学术带头人。在排队论、非线性最优化和组合优化方面取得了多项国际领先水平的重要研究成果。
目录
译者序
第四版序言
第三版序言
第二版序言
第一版序言
符号表
第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
符号表
自然数集
{1, 2, 3, ···}
(非负)整数集(非负)有理数集(非负)实数集真子集子集不交并集合X与Y的对称差向量x的欧氏范数向量x的无穷范数唯一数z使得0.z
x.z
向量x与矩阵A的转置不严格小于x的最小整数不严格大于x的最大整数O表示法Θ表示法x的编码长度;x的二进制字符串长度x以2为底的对数图G的顶点集图G的边集由X. V(G)诱导的G的子图图G中由V(G)\{v} 诱导的子图图G删去边e的子图图G添加边e后的图图G和H的并集在图G中将顶点集X收缩成单点所得的生成图两端点分别在顶点集X\ Y 和Y \ X 的边集顶点集X \ Y 到Y \ X的有向边集E(X,V(G)\ X),E({v},V(G)\{v})顶点集X的邻点集,顶点v的邻点集顶点集X的出边集,顶点v的出边集顶点集X的入边集,顶点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个顶点的完全图路径P的x-y子路径最短v-w路径的长度.c(e)(假设c:ER以及F. E)
→
e∈F
n个和m个顶点构成的完全二分图多胞形J与直线l的交点数图G的平面对偶图图G. 的一条边;边e的对偶向量x与y的内积给定向量x和y,不等号在x和y的每个分量上成立矩阵A的秩非空集X. Rn 的维数单位阵j-单位向量(第j个分量为1,其余为0)由矩阵A中J的对应行组成的子矩阵由向量b中指标集J对应元素组成的子向量各分量均为1的向量由矩阵A中指标集J所对应列组成的子矩阵集合X中所有向量的凸包矩阵A的行列式排列π的符号函数椭球欧氏空间中以x为圆心、r为半径的球非空集X. Rn 的容积矩阵A的范数集合X的极点集多胞形P的整数包矩阵A子行列式的最大绝对值P的1阶,i阶Gomory-Chv′atal割体拉格朗日松弛多割边(x,y)关于π所降低的费用(G,c)在度量空间中的闭包顶点v的入流
书单推荐
