欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.
英文摘要：
A new variant of the min-cost bin covering problem （min-cost BCP） has been proposed, in which each item has two parameters, capacity and cost. For the offline min-cost BCP, we have presented an algorithm C-FF1. It has been proved that the C-FF1 algorithm has an asymptotic worst - case performance ratio of 1/2. For the online min-cost BCP, we have also presented an online algorithm C-FF2 with an absolute worst-case ratio 1/ 2. Moreover, we have provided lower worst-case bounds of any online and offline algorithms.
同期刊论文项目
同项目期刊论文
位置：