近似算法的设计
David P. Williamson
The Design of Approximation
Algorithms
2022,520pp
Hardback
近似算法的设计
David P. Williamson
The Design of Approximation
Algorithms
2022,520pp
Hardback
ISBN9780521195270
离散优化问题随处可见, 从传统的运筹学规划问题，到数据库中的计算机科学问题，再到病毒式营销的通知问题。大多数这样的问题都是NP困难问题，也就是说除了P=NP以外，并不存在寻找此类问题最佳解的有效算法。这本书说明了怎样设计近似算法：即发现可证明的近似最优解有效算法。本书的内容是围绕着近似算法设计的重要算法技术展开的，其中包括了贪婪及局部搜寻算法、动态规划、线性及半定规划以及随机化。本书的第一部分中的每一章均专注于单一的算法技术，然后把这些技术应用于若干不同的问题中。本书的第二部分重返这些技术，但是作者提供了对这些技术的更高层次的论述。本书还涉及了用来证明优化问题难以近似的方法。
本书共有17章，分成二个部分。第1部分 技术入门，包括第1-8章，；；；；；；-对偶方法；。第2部分 技术的进一步应用，包括第9-17章，；；；；；-对偶方法的进一步应用；；；。最后是附录A 线性规划。附录B NP完全性。
本书的第一作者是康奈尔大学跨运筹学与信息工程学院及信息科学系的教授。在加入康奈尔大学之前，
近似算法的设计 来自淘豆网m.daumloan.com转载请标明出处.
