Discrete optimization algorithms

第一章线性规划
1.1线性规划的基本概念
1.2单纯形算法
1.3线性规划的对偶理论
1.4对偶单纯形算法
1.5原始一对偶算法
1.6单纯形算法是非多项式算法
1.7线性规划问题的多项式时间算法
习题
参考文献
第二章整数线性规划
2.1 引言
2.2分数对偶割平面算法
2.3整数对偶割平面算法
2.4混合整数规划的割平面算法
2.5分支估界算法
2.6 0-1规划的隐数法（implicit enumeration）
习题
参考文献
第三章网络规划
3.1图的搜索算法
3.1.1无向图的深探法（DFS）
3.1.2无向图的广探法（BFS）
3.2网络流模型及解的整数性
3.3网络中的最短路
3.3.1非负权网络的最短路算法
3.3.2无负回路网络中的最短路算法
3.3.3所有点对之间的最短路算法
3.4网络中的最大流
3.4.1最大流的Ford—Fulkerson算法
3.4.2最大流的Dinits算法
3.4.3容量具有上下界的最大流算法
3.4.4可行性定理及其组合应用
3.5最小费用流
3.5.1模型Ⅱ的相继最短路算法
3.5.2最小费用循环流的平均圈算法
习题
参考文献
第四章树与拟阵
4.1树的基本性质
4.2树的中心与重心
4.3无向网络中的最优生成树
4.4有向树
4.5拟阵的基本概念与性质
4.5.1拟阵的定义与例子
4.5.2拟阵的一些基本性质
4.6拟阵与Greedy算法
4.7拟阵的最大交
4.8最大权交的算法
习题
参考文献
第五章动态规划
5.1网络中两点间的最优路问题
5.2用动态规划方法解某些非线性规划
5.3用动态规划方法解某些整数规划
5.4生产计划与资源分配问题
5.4.1生产计划问题
5.4.2资源分配问题
5.5排序问题
5.5.1排序问题
5.5.2货郎问题
5.6矩阵链与公共子序列
5.6.1矩阵链中矩阵相乘的顺序问题
5.6.2最长公共子序列问题
习题
参考文献
第六章逆最优化问题
6.1逆线性规划的一般模型
6.2在范数l1下式（6.1.5）和式（6.1.6）的解
6.2.1给定的可行解X0为0—1的解
6.2.2在范数l1下模型LP2的解
6.3在范数l∞下式（6.1.5）和式（6.1.6）的解
6.4组合优化的逆问题一般模型
6.5各种逆最优化问题的归结
6.6瓶颈扩张问题的一例
习题
参考文献
第七章算法、复杂性与NP—完全理论
7.1问题、算法与复杂性
7.2多项式算法P类和NP类
7.3多项式变换与NPC类
7.4 NP—完全问题的证明举例
7.5关于NP—完全性的另一些概念
7.5.1 Co—NP类
7.5.2 NP—hard类
7.5.3伪多项式算法与强NP—完全性
习题
参考文献
第八章近似算法及其分类
8.1近似算法的基本概念
8.2非空闲策略
8.3 Greedy算法
8.4局部搜索
8.5基于线性规划的近似算法
8.6基于动态规划的近似算法
8.7绝对近似类
8.8相对近似类
8.9 PTAS类与FPTAS类
8.10随机近似算法
8.11近似算法的概率分析
习题
参考文献