全新正版 网络流算法 (美)大卫·P.威廉姆森|责编:曲熠|译者:吴向军 9787111701071 机械工业

拾人花卉，系之一束；他供鲜花，我献彩带。 
——Montaigne 

网络流方面的任何新书似乎都应说明其存在的合理性，因为该领域的权威著作早已出版。我所参考的书籍《网络流：理论、算法和应用》(Network Flows: Theory, Algorithms, and Applications) 已于 1993 年出版。该书作者为 Ahuja、Magnanti 和 Orlin[4]，他们是网络流算法领域理论研究和实践应用的先驱。我用该书作者姓名的首字母 AMO 来代表此书。20 世纪 80 年代末至 90 年代初是研究网络流问题的组合算法和多项式算法的黄金时期。AMO 不仅讨论了当时已完成的大部分研究，还给出了网络流领域的广泛综述，其内容贯穿网络流理论研究和实际应用。既然如此，为何还需写此书？我有下面三方面的理由。 
：关注点问题。我在写另一领域的严谨性书籍 [206] 时意识到，书籍内容很难兼顾“准确严谨” 和 “简洁明了”。AMO 无疑是前者，本书的目标是后者。本书主要关注网络流问题的组合算法、多项式算法及其分析。在康奈尔大学运筹学和信息工程学院任教期间，我教过几次网络流算法方面的研究生课程，本书内容源于对这些课程内容的提炼。该课程主要面向运筹学和计算机科学系的学生，也有电气和土木工程系的部分学生。从教学观点来看，需做点取舍，以保证本书的大部分内容可在一学期内讲完。 
此外，由于本书是课堂教学的成果，其涵盖的知识点是一次授课所能讲完的内容。因此，太长或太复杂而无法在一次授课中讲完的知识点，本书都不涵盖。我不太关注网络流理论中的某些领域，比如没有多项式运行时间的网络流应用和算法等。对于本书未涉及的某些网络流理论部分，感兴趣的读者可参阅 AMO。 
第二：提供一些 AMO 没有涉及的知识。对流问题和小代价环流问题，虽然本书所提的算法 AMO 也有涉及，但本书给出了一些重要的特殊情形。如前所述，虽然 20 世纪 80 年代末至 90 年代初是研究网络流算法的黄金时代，但该领域在过去 25 年里的研究成果是 AMO 无法涵盖的。 
1998 年，Goldberg 和 Rao 所发表的论文 [98] 就是一个著名的研究成果。对流问题，他们给出了至今为止在理论上仍被认为快的算法。1991 年，Wallacher[201] 关于小代价环流问题的算法是另一个研究成果，该算法具有相当简单的分析。此外，AMO 出版时，针对某些流问题，一些多项式算法正好脱颖而出。显然，AMO 无法涵盖这些算法。 
我主要思考的是全局小割集、广义流和多物流等问题的算法。近年来，内点方法在网络流问题的特殊应用中产生了一些快速算法，但这些算法不是组合算法，因此，它们不在本书的选取范围内。本书还包含了一些与电流经典主题相关的成果。 
第三：情不自禁。我的主要研究兴趣是组合算法和多项式算法，但在网络流领域，除有一项研究成果外 [173]，几乎一无所获。所以，作为一位公正的旁观者，我可以说，该领域是一个优美且存在一些有用算法思想的领域，这些算法思想以一种令人愉悦的方式相互支持着。 
用前面引述的 Montaigne 的话来说，写本书的目的就是做选择和重组，尽我所能地展现一些算法及其分析的美妙之处。希望读者和我一样欣赏这终呈现的花束。 

David P. Williamson 
纽约，伊萨卡 
2019 年 1 月

网络流理论在理论计算机科学、运筹学和离散数学等学科中均有应用，可用于货物运输建模和计算机视觉图像分割等众多问题。本书主要源于康奈尔大学的网络流算法课程讲义，包含出版年代较早的经典书籍中未能涵盖的新研究成果。本书采用简洁且统一的视点，讨论解决网络流问题的多种组合算法、多项式算法及其分析，涵盖流、小代价流、广义流、多物流和全局小割集等，还介绍了关于计算电流的新研究成果及其在经典问题上的应用。本书可作为面向研究生的网络流算法教材，也适合该领域的研究人员参考。