近似算法的设计.docx

《近似算法的设计.docx》由会员分享，可在线阅读，更多相关《近似算法的设计.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、近似算法的设计 David P. Williamson The Design of Approximation Algorithms 2022,520pp Hardback ISBN10180521195273 离散优化问题随处可见, 从传统的运筹学规划问题，到数据库中的计算机科学问题，再到病毒式营销的通知问题。大多数这样的问题都是NP困难问题，也就是说除了P=NP以外，并不存在找寻此类问题最佳解的有效算法。这本书说明白怎样设计近似算法：即发觉可证明的近似最优解有效算法。本书的内容是围围着近似算法设计的重要算法技术绽开的，其中包括了贪欲及局部搜寻算法、动态规划、线性及半定规划以及随机化。本书的

2、第一部分中的每一章均专注于单一的算法技术，然后把这些技术应用于若干不同的问题中。本书的其次部分重返这些技术，但是作者供应了对这些技术的更高层次的论述。本书还涉及了用来证明优化问题难以近似的方法。 本书共有17章，分成二个部分。第1部分 技术入门，包括第1-8章，1.近似算法介绍；2.贪欲算法与局部搜寻；3.舍入数据与动态规划；4.线性规划的确定舍入；5.随机抽样与线性规划的随机性舍入；6.半定程序的随机性舍入；7.主要-对偶方法；8.分割与度量。第2部分 技术的进一步应用，包括第9-17章，9.贪欲与局部搜寻的进一步应用；10.舍入数据与动态规划的进一步应用；11.线性规划的确定舍入的进一步应

3、用；12.随机抽样与线性规划的随机性舍入的进一步应用；13.半定程序随机性舍入的进一步应用；14.主要-对偶方法的进一步应用；15.分割与度量的进一步应用；16.用来证明近似硬度的技术；17.公开问题。最终是附录A 线性规划。附录B NP完全性。 本书的第一作者是康奈尔高校跨运筹学与信息工程学院及信息科学系的教授。在加入康奈尔高校之前，他是IBM 的T•J•沃森探讨中心探讨员和IBM的Almaden探讨中心资深经理。由于他在近似算法方面的工作，获得了美国数学协会和数学规划学会颁发的2000年度Fulkeron 奖及其它的若干奖项。本书的其次作者同样是康奈尔高校运筹学与信

4、息工程学院和计算机科学系的教授，他还兼任康奈尔高校计算可持续性探讨所的副主任。他是美国计算机协会的会员，曾是美国自然科学基金总统青年探讨员。 本书适用于探讨生程度算法课程，同时也可以用作那些对离散优化问题启发解法感爱好的探讨人员的参考书。 胡光华， 退休高工 (原中国科学院物理学探讨所) Hu Guanghua, Senior Software Engineer (Former Institute of Physics,CAS) 第3页 共3页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页