组合最优化:理论与算法

本书大致分为两部分。第一部分侧重基础，介绍了线性规划的理论和算法，整数规划、各种树、最短路与网络流等；第二部分侧重组合优化中的一些重要分支，如网络流、匹配、网络设计、旅行者问题、多种物资流等。本书得到了越民义、修乃华、张国川等专家的大力推荐。

译者序
第四版序言
第三版序言
第二版序言
第一版序言
符号表
第1章引言
1.1枚举法
1.2算法的运行时间
1.3线性优化问题
1.4整序
习题
参考文献
第2章图
2.1基本定义
2.2树，圈和截
2.3连通性
2.4欧拉图和二部图
2.5可平面性
2.6平面对偶性
习题
参考文献
第3章线性规划
3.1多面体
3.2单纯形法
3.3单纯形法的执行
3.4对偶性
3.5凸包和多面体
习题
参考文献
第4章线性规划算法
4.1顶点和面的尺寸
4.2连分数
4.3高斯消去法
4.4椭球法
4.5 Khachiyan定理
4.6分离和优化
习题
参考文献
第5章整数规划
5.1多胞形的整数闭包
5.2单模变换
5.3全对偶整性
5.4全单模矩阵
5.5割平面
5.6拉格朗日松弛
习题
参考文献
第6章支撑树和树形图
6.1最小支撑树
6.2最小树形图
6.3多面体描述
6.4储存支撑树和树形图
习题
参考文献
第7章最短路
7.1一个起点的最短路
7.2全部点对间的最短路
7.3最小平均圈
习题
参考文献
第8章网络流
8.1优选流一最小截定理
8.2 Menger定理
8.3Edmonds—Karp算法
8.4阻塞流与Fujishige算法
8.5 Goldberg—Tarjan算法
8.6 Gomory—Hu树
8.7无向图的最小容量截
习题
参考文献
第9章最小费用流
9.1问题表述
9.2很优性准则
9.3最小平均圈消去算法
9.4逐次最短路算法
9.5 Orlin算法
9.6网络单形算法
9.7时变流
习题
参考文献
第10章优选匹配
10.1二部图匹配
10.2 Tutte矩阵
10.3 Tutte定理
10.4因子临界图的耳分解
10.5 Edmonds匹配算法
习题
参考文献
第11章加权匹配
11.1分配问题
11.2加权匹配算法概述
11.3加权匹配算法的实现
11.4后续优化
11.5匹配多面体
习题
参考文献
第12章 b—配与T—连接
12.1 b—配
12.2最小权T—连接
12.3 T—连接与T—截
12.4 Padberg—Rao定理
……
第13章拟阵
第14章拟阵的推广
第15章NP完备性
第16章近似算法
第17章背包问题
第18章装箱问题
第19章多商品流和边不重路
第20章网络设计问题
第21章旅行商问题
第22章选址问题
名词索引
《现代数学译丛》已出版书目