互联网信息组织和规划中的带拒绝装箱问题  

Bin Packing Problem with Rejection in the Information Organization and Allocation of Internet and Web

作　　者：何勇[1] 谈之奕[1] 任峰[1] 

机构地区：[1]浙江大学数学系

出　　处：《计算机学报》2003年第12期1765-1770,共6页Chinese Journal of Computers

基　　金：高等学校优秀青年教师教学科研奖励计划;国家自然科学基金(1 0 2 71 1 1 0 );国家"九七三"重点基础研究发展规划项目 (1 9980 30 4 0 1 )资助

摘　　要：讨论如下定义的带拒绝装箱问题 :设有许多等长的一维箱子 ,给定一个物品集 ,每个物品有两个参数 :长度和罚值 .物品可以放入箱子也可被拒绝放入箱子 .如果将物品放入箱子 ,则使该箱剩余长度减少 .一旦需将某一物品放入某一箱中 ,而该箱的剩余长度不够时 ,则需启用新箱子 .如果物品被拒绝放入任何箱中 ,则产生惩罚 .问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小 .该问题是一个新的组合优化问题 ,来源于内部互联网的信息组织和规划 .该文首先给出一个最优解值的下界估计 ,它可用于分枝定界法求最优解 .由于该问题是强NP 难的 ,该文进一步研究它的离线和在线近似算法的设计与分析 .文中给出一个离线算法 ,其绝对性能比为 2 ;同时给出一个在线算法 ,其绝对性能比不超过 3 ,渐近性能比为 2 ,还对算法性能比的下界进行了讨论 .In this paper, we consider the following bin packing problem with rejection. We are given n items, each with a capacity and penalty, and unlimited bins with equal capacity. An item can be either rejected, in which case we pay its penalty, or put in one of the bins, in which case it causes the decreasing of the capacity of a certain bin. The objective is to minimize the sum of the number of the used bins and the penalties of all rejected items. This is a new combinatorial optimization problem which has many applications in practice, such as in organizing and allocating information on web servers. We first provide a lower bound of its optimal value which can be used to solve the problem optimally by branch and bound method. Since the problem is strongly NP-hard, we further consider the design and analysis of its online and offline approximation algorithms. We present an offline algorithm with absolute worst case ratio 2, and an online algorithm with asymptotic worst case ratio 2 and absolute worst case ratio no greater than 3. Moreover we provide lower worst-case bounds of any online and offline algorithms.

关 键 词：互联网 信息组织 信息规划 装箱问题 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]