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

• 作者: 任峰 何勇 谈之奕
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 装箱问题 算法设计与分析 近似算法 因特网通信 信息管理
• 年，卷（期）: 2003,（12）
• 所属期刊栏目: 短文
• 页码范围: 1765-1770
• 页数: 6页
• 分类号: TP393
• 字数: 6139字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2003.12.023

摘要

讨论如下定义的带拒绝装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和罚值.物品可以放入箱子也可被拒绝放入箱子.如果将物品放入箱子,则使该箱剩余长度减少.一旦需将某一物品放入某一箱中,而该箱的剩余长度不够时,则需启用新箱子.如果物品被拒绝放入任何箱中,则产生惩罚.问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,来源于内部互联网的信息组织和规划.该文首先给出一个最优解值的下界估计,它可用于分枝定界法求最优解.由于该问题是强NP-难的,该文进一步研究它的离线和在线近似算法的设计与分析.文中给出一个离线算法,其绝对性能比为2;同时给出一个在线算法,其绝对性能比不超过3,渐近性能比为2,还对算法性能比的下界进行了讨论.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	任峰	浙江大学数学系	1	7	1.0	1.0