David P. Williamson
The Design of Approximation
Algorithms
2011,520pp
Hardback
ISBN9780521195270
离散优化问题随处可见, 从传统的运筹学规划问题，到数据库中的计算机科学问题，再到病毒式营销的通知问题。大多数这样的问题都是NP困难问题，也就是说除了P=NP以外，并不存在寻找此类问题最佳解的有效算法。这本书说明了怎样设计近似算法：即发现可证明的近似最优解有效算法。本书的内容是围绕着近似算法设计的重要算法技术展开的，其中包括了贪婪及局部搜寻算法、动态规划、线性及半定规划以及随机化。本书的第一部分中的每一章均专注于单一的算法技术，然后把这些技术应用于若干不同的问题中。本书的第二部分重返这些技术，但是作者提供了对这些技术的更高层次的论述。本书还涉及了用来证明优化问题难以近似的方法。
本书共有17章，分成二个部分。第1部分 技术入门，包括第1-8章，1.近似算法介绍；2.贪婪算法与局部搜寻；3.舍入数据与动态规划；4.线性规划的确定舍入；5.随机抽样与线性规划的随机性舍入；6.半定程序的随机性舍入；7.主要-对偶方法；8.分割与度量。第2部分 技术的进一步应用，包括第9-17章，9.贪婪与局部搜寻的进一步应用；10.舍入数据与动态规划的进一步应用；11.线性规划的确定舍入的进一步应用；12.随机抽样与线性规划的随机性舍入的进一步应用；13.半定程序随机性舍入的进一步应用；14.主要-对偶方法的进一步应用；15.分割与度量的进一步应用；16.用来证明近似硬度的技术；17.公开问题。最后是附录A 线性规划。附录B NP完全性。
本书的第一作者是康奈尔大学跨运筹学与信息工程学院及信息科学系的教授。在加入康奈尔大学之前，他是IBM 的T•J•沃森研究中心研究员和IBM的Almaden研究中心资深经理。由于他在近似算法方面的工作，获得了美国数学协会和数学规划学会颁发的2000年度Fulkeron 奖及其它的若干奖项。本书的第二作者同样是康奈尔大学运筹学与信息工程学院和计算机科学系的教授，他还兼任康奈尔大学计算可持续性研究所的副主任。他是美国计算机协会（ACM）的会员，曾是美国自然科学基金总统青年研究员。
本书适用于研究生程度算法课程，同时也可以用作那些对离散优化问题启发解法感兴趣的研究人员的参考书。
胡光华，
退休高工
(原中国科学院物理学研究所)
Hu Guanghua, Senior Software Engineer
(Former Institute of Physics,CAS)