---作者简介---
大卫·P. 威廉姆森（David P. Williamson） 康奈尔大学运筹学和信息工程学院教授，ACM会士，SIAM会士。他在离散优化方面的研究获得了多个奖项，包括2000年由美国数学协会和数学规划协会赞助的Fulkerson奖。他与David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge, 2011）获得了2013年的INFORMS Lanchester奖。他在多个编委会任职，曾任SIAM Journal on Discrete Mathematics的主编。

---译者简介---
吴向军 博士，中山大学副教授。主要研究方向为人工智能和算法设计等，近年来主要从事智能规划领域的研究和规划系统的设计与开发。

译者序
前言
致谢
第 1 章 预备知识：最短路径算法 1
1.1 无负权边：Dijkstra 算法 2
1.2 有负权边：Bellman-Ford算法 5
1.3 负权回路的检测算法 9
练习 16
章节后记 17
第 2 章 最大流算法 19
2.1 最优化条件 21
2.2 应用：汽车共享问题 27
2.3 应用：棒球队淘汰问题 28
2.4 应用：最密子图问题 33
2.5 最大改进增广路径算法 37
2.6 容量度量算法 40
2.7 最短增广路径算法 42
2.8 推送–重标算法 44
练习 54
章节后记 59
第 3 章 全局最小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 随机合并算法 72
3.4 Gomory-Hu 树 76
练习 83
章节后记 85
第 4 章 其他最大流算法 88
4.1 阻塞流算法 88
4.2 单位容量图的阻塞流 90
4.3 Goldberg-Rao 算法 92
练习 96
章节后记 97
版权声明 97
第 5 章 最小代价环流算法 99
5.1 最优化条件 101
5.2 Wallacher 算法 104
5.3 最小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 网络单纯形 124
5.7 应用: 带时限的最大流问题 126
练习 130
章节后记 136
第 6 章 广义流算法 139
6.1 最优化条件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 负代价 GAP 检测 151
6.4 有损图、Truemper 算法和收益度量 155
6.5 误差度量 161
练习 163
章节后记 164
第 7 章 多物流算法 166
7.1 最优化条件 166
7.2 双物流问题 168
7.3 预备知识：乘权算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
练习 184
章节后记 185
第 8 章 电流算法 187
8.1 最优化条件 187
8.2 无向图的最大流问题 196
8.3 图的稀疏化 199
8.4 简易 Laplacian 求解器 204
练习 210
章节后记 212
版权声明 213
第 9 章 开放问题 214
参考文献 216