|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 弱问：什么是2-approximation algorithm或x--approximation，在什么书里能找到 (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=41170) |
|
-- 作者：justforthis -- 发布时间：12/13/2006 2:03:00 PM -- 弱问：什么是2-approximation algorithm或x--approximation，在什么书里能找到 弱问：什么是2-approximation algorithm或x--approximation，在什么书里能找到 |
|
-- 作者：Logician -- 发布时间：12/13/2006 3:39:00 PM -- 对某个最优化问题（这个最优化问题既可以是“寻找使cost最大的方案”的问题，也可以“寻找使cost最小的方案”的问题）的某个实例x，若最优解的cost是OPT(x)，而用某近似算法为该问题找到的解M(x)的cost是c(M(x))。如果该近似算法能确保： |c(M(x)) - OPT(x)| -------------------- ≤ k max{OPT(x),c(M(x))} 就称这个近似算法是k-approximation algorithm。 相关内容可以看Christos H. Papadimitriou写的Computational Complexity。 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |