互联网信息管理中的带拒绝装箱覆盖问题

作     者：杨鼎强 王晨 YANG Ding-qiang;WANG Chen

作者机构：长沙理工大学计算机与通信工程学院湖南长沙410076 中国湖南国际经济技术合作公司湖南长沙410001 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2007年第28卷第10期

页      码：2453-2454,2457页

摘      要：作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子。每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出了一个求解该问题的局外近似算法C-FF,分析其最坏情况渐进性能比为1/2,并给出了相应的实验结果。

主 题 词：装箱覆盖问题 近似算法 最坏情况渐进性能比 因特网通信 信息管理 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-7024.2007.10.065

馆 藏 号：203932381...