请教一个算法的问题
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 13 楼,当前显示第 5 楼 : 从楼主开始阅读 : 本帖树形列表 : 返回上一页
作者:马甲甲甲 (等级:6 - 驾轻就熟,发帖:1503) 发表:2006-02-27 23:18:00  5楼  评分: 
approximation algorithm
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.
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

本帖共有 13 楼,当前显示第 5 楼,本文还有 N-1 层楼,要不你试试看:点击此处阅读更多 >>



请登录后回复:帐号   密码