《组合优化》以通畅而连贯的讲解、基本和高深概念的清晰解释、众多现实生活中的实例、以及颇有助益的技巧训练习题为特征，一定会成为未来许多年里本领域内 的标准教科书。组合优化，作为应用数学中最年轻而又至关重要的领域之一，整合了组合数学、线性规划以及算法理论的方法和技巧。由于它在解决从远程通讯到超 大规模集成电路、从产品运销到航班机组排班等领域内困难问题方面的成功，这一领域在过去的十年里取得了巨大的、超乎寻常的发展。库克等著的《组合优化》是 对这一数学分支的一个理想介绍，它适用于离散数学、计算机科学以及运筹学专业的本科高年级学生和研究生。《组合优化》由公认的专家团队撰写而成，对经典概念和最新结果都提供了全面而又易懂的讲解。主要涉及以下课题：网络流问题、最优匹配、多面体的整性、拟阵、NP-完全性。
- 目录
- 前辅文
- 第一章 问题和算法
- 第二章 最优树和最优路
- 第三章 最大流问题
- 3.1 网络流问题
- 3.2 最大流问题
- 3.3 最大流和最小割的应用
- 3.4 压入重标记最大流算法
- 3.5 无向图中的最小割
- 3.6 多商品流
- 第四章 最小费用流问题
- 4.1 最小费用流问题
- 4.2 原始最小费用流算法
- 4.3 对偶最小费用流算法
- 4.4 对偶尺度放大算法
- 第五章 最优匹配
- 5.1 匹配和交错路
- 5.2 最大匹配
- 5.3 最小权完美匹配
- 5.4 T-连接和邮递员问题
- 5.5 一般匹配问题
- 5.6 几何对偶和Goemans-Williamson 算法
- 第六章 多面体的整性
- 6.1 凸包
- 6.2 有界多面体
- 6.3 侧面
- 6.4 整有界多面体
- 6.5 全幺模性
- 6.6 全对偶整性
- 6.7 割平面
- 6.8 分离与优化
- 第七章 旅行售货商问题
- 7.1 引言
- 7.2 TSP 的启发式方法
- 7.3 下界
- 7.4 割平面
- 7.5 分支定界
- 第八章 拟阵
- 8.1 拟阵及贪婪算法
- 8.2 拟阵: 性质, 公理, 构造
- 8.3 拟阵交
- 8.4 拟阵交的应用
- 8.5 赋权拟阵交
- 第九章 NP和NP-完全性
- 9.1 引言
- 9.2 字
- 9.3 问题
- 9.4 算法和运行时间
- 9.5 NP 类
- 9.6 NP-完全性
- 9.7 适定性问题的NP-完全性
- 9.8 一些其他问题的NP-完全性
- 9.9 图灵机
- 附录A 线性规划
- 参考文献
- 名词索引
- 版权
