approximation algorithm for NP hard problem

近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解，并使其目标函数值与最优解的目标函数值之比不超过一个常数。本书将通过大量具有代表性的组合优化问题，介绍近似算法设计和分析中的三种主要方法：贪婪算法、限制方法和松弛方法；所讨论的问题来源于不同的研究和应用领域，其中包括通信网络设计，光纤网络，无线自组织网络和传感器网络，生物信息学，社会网络，工业工程和信息管理系统等。