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

第35卷 第2期 湖 南 大 学 学 报 (自然 科学版) Vo1．35，No．2 2 0 0 8年 2月 Journal of Hunan University(Natural Sciences) Feb．2 0 0 8 文章编号：1000—2472(2008)02—0077—03 最小费用箱子覆盖 问题 及其算法 杨鼎强 ，谢冬青 (1．湖南大学计算机与通信工程学院，湖南长沙 410082；2．长沙理工大学计算机与通信工程学院，湖南长沙 410076) 摘 要：提出了一种有实际背景的最小费用箱子覆盖问题一一每个物品有长度和费用 2个参数．针对局外最小费用箱子覆盖问题，给出了一个求解该问题的最坏情况渐近性能比 为1／2算法C—FF．．同时给出了一个求解该问题的局内算法C—FF2，其绝对性能比为1／2， 并证明了不存在绝对性能比大于1的算法． 关键词：近似算法；箱子覆盖问题；组合优化；渐近性能比 中图分类号：TP301 文献标识码：A Min—cost Bin Covering Problem and Its Algorithm YANG D!ng—qiang - ，XIE Dong—qing (1．College of Computer and Communication，Hunan Univ，Changsha，Hunan 410082，China； 2． of Computer and Communication Engineering，Cha~ha Univ of Science and Techndogy，a扭n ha，Hunan 410076，China) Abstract：A new variant of the min—cost bin coveri ng 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—FFI．It has been proved that the C—FFI algorithm has an asymptotic worst—case perfc-rmance 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． Key words：approximation algorithms；bin covering problem；combinational optimization；asymptotic com— petitive ratio 装箱问题在多处理器任务调度 、并行处 ing Problem，简称min—cOSt BCP)． 理 、资源分配和现实生活中的包装等问题中有 注意到如果令每个物品的费用都充分大，该问 着广泛的应用背景，一系列装箱问题的衍生问题也 题就退化为箱子覆盖问题．它是强NP难的 ，因此 逐步被关注和研究，如箱子覆盖问题 ． 最小费用箱子覆盖问题也是强NP难的．由于目前 本文提出一种新的箱子覆盖问题：给定 个物 NP完全问题不存在有效时间内求得精确解的算 品的序列L =(a，，a ，…，a )，物品a (1≤i≤ ) 法，因此设计与分析