approximation algorithm
所在版块:求学狮城 发贴时间:2006-02-27 23:18  评分:

用户信息
复制本帖HTML代码
高亮: 今天贴 X 昨天贴 X 前天贴 X 
This bin-pack problem is extensively used as an example for approximation algorithms in NP-complete problems. You should be able to find the explainations and proofs (for both FF and FFD) in a reasonable college computer algorithm textbook, under NP-complete section, but it might not be covered in an undergraduate algorithm course.

Briefly put, given an optimal solution of value O to an NP problem, and an approximation algorithm (in polynomial time) that outputs a solution that is k*O on average, then this approximation algorithm is called a k-approximation.

If I remember correctly, FFD is an 3/2 approximation algorithm.
.
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!

 相关帖子 我要回复↙ ↗回到正文
请教一个算法的问题 noah   (614 bytes , 750reads )
你是请教新生,还是混充新生请教? Bird   (0 bytes , 208reads )
本来想打电话问你的,不过明天我有考试,你说你看见了就简单得作答一下子呗 noah   (0 bytes , 226reads )
oh.... Bird   (557 bytes , 263reads )
呵呵,替新生谢过 noah   (0 bytes , 189reads )
我是那位2006届SM3新生 Buniverse   (58 bytes , 271reads )
我帮新生请教 noah   (0 bytes , 172reads )
approximation algorithm 马甲甲甲   (630 bytes , 408reads )
谢谢“这么多马甲”同学,呵呵 noah   (0 bytes , 286reads )
装箱问题 ? 奕丫   (351 bytes , 345reads )
传说中用动态规划...晕了,两年没看过了 奕丫   (0 bytes , 358reads )
不一样。。。 Bird   (0 bytes , 202reads )
先问一个问题: 奕丫   (216 bytes , 248reads )