《计算机学报》文章摘要   全文下载
文章题目	互联网信息组织和规划中的带拒绝装箱问题
作者	何勇1），2） 谈之奕1），2） 任峰1）
作者单位	1）（浙江大学数学系 杭州 310027） 2）（浙江大学CAD　&　CG国家重点实验室 杭州 310027）
发表年份	2003
发表月份	12期(页码：1765-1770)
文章摘要	摘要 讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子, 给定一个物品集，每个物品有两个参数：长度和罚值.物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子, 则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题, 来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计, 它可用于分枝定界法求最优解. 由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法, 其绝对性能比为2；同时给出一个在线算法, 其绝对性能比不超过3, 渐近性能比为2，还对算法性能比的下界进行了讨论. 关键词 装箱问题；算法设计与分析；近似算法；因特网通信；信息管理 中图法分类号 TP393