一类带多重核元集在线装箱问题

• 作者: 帅天平 胡晓东
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: 装箱 在线算法 核元 性能界
• 年，卷（期）: 2005,（3）
• 页码范围: 411-416
• 页数: 6页
• 分类号: O223
• 字数: 4430字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9847.2005.03.013

摘要

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NP-Hard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡晓东	中国科学院数学与系统科学研究院	59	791	16.0	26.0
2	帅天平	中国科学院数学与系统科学研究院	2	6	2.0	2.0