近似算法

发表于 2020-06-15| 更新于 2020-10-27

阅读量:

近似算法要求

时间：多项式时间
近似比：常数

假设P!=NP,NP-hard组合优化问题可以按近似性分为三类：

完全可近似的，对于任意小$\varepsilon $d,存在(1+$ \varepsilon $)的近似算法，比如背包问题
可近似的，存在具有常数比的近似算法，例如最小顶点覆盖，多级问题
不可近似的不存在具有常数比的近似算法，比如货郎问题

最小顶点覆盖

Steiner tree

文章作者: Sunxin

文章链接: https://sunxin18.github.io/2020/06/15/app/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lalala！

微信
支付宝

评论