第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.3 Edmonds-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章 拟阵

13.1独立系统与拟阵

13.2另外的拟阵公理

13.3对偶

13.4贪婪算法

13.5拟阵交

13.6拟阵划分

13.7加权拟阵交

习题

参考文献

第 14章 拟阵的推广

14.1广义拟阵

14.2拟阵多面体

14.3求次模函数的最小值

14.4 Schrijver算法

14.5对称次模函数

习题

参考文献

第15章NP完备性

15.1 Turing机

15.2 Church的论题

15.3 P与NP

15.4 Cook定理

15.5某些基本的NP完备问题

15.6 coNP类

15.7 NP难问题

习题

参考文献

第16章 近似算法

16.1集覆盖

16.2 Max-Cut（最大割）问题

16.3着色

16.4近似方案

16.5最大可满足性

16.6 PCP定理

16.7 L归约

习题

参考文献

第17章 背包问题

17.1分数型背包问题和赋权中位问题

17.2伪多项式算法

17.3一个全多项式近似方案

习题

参考文献

第18章 装箱问题

18.1贪婪算法

18.2渐近近似方案

18.3 Karmarkar-Karp算法

习题

参考文献

第19章 多商品流和边不重路

19.1多商品流

19.2多商品流算法

19.3有向的边不重路问题

19.4无向的边不重路问题

习题

参考文献

第20章 网络设计问题

20.1 Steiner树

20.2 Robins- Zelikovsky算法

20.3可靠网络设计

20.4原始对偶近似算法

20.5 Jain算法

习题

参考文献

第21章 旅行商问题

21.1旅行商问题的近似算法

21.2欧氏平面上的旅行商问题

21.3局部搜索

21.4旅行商多面体

21.5下界

21.6分枝定界

习题

参考文献

第22章 选址问题

22.1无容量限制的设施选址问题

22.2基于线性规划的舍入算法

22.3原始对偶算法

22.4放缩与贪婪增广方法

22.5界定设施的数目

22.6局部搜索

22.7有容量限制的设施选址问题

22.8设施选址问题的一般模型

习题

参考文献

名词索引

《现代数学译丛》已出版书目