最小费用箱子覆盖问题及其算法  

Min-cost Bin Covering Problem and Its Algorithm

作　　者：杨鼎强[1] 谢冬青[1] 

机构地区：[1]湖南大学计算机与通信工程学院

出　　处：《湖南大学学报（自然科学版）》2008年第2期77-79,共3页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金资助项目(20676154);湖南省教育厅资助科研项目(06C126)

摘　　要：提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用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.

关 键 词：近似算法 箱子覆盖问题 组合优化 渐近性能比 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]