最小费用箱子覆盖问题及其算法

• 作者: 杨鼎强 谢冬青
• 来源期刊: 湖南大学学报（自然科学版）
• 关键词: 近似算法 箱子覆盖问题 组合优化 渐近性能比
• 年，卷（期）: 2008,（2）
• 所属期刊栏目: 计算机科学与工程
• 页码范围: 77-79
• 页数: 3页
• 分类号: TP301
• 语种: 中文

摘要

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢冬青	湖南大学计算机与通信工程学院	77	488	11.0	17.0
2	杨鼎强	湖南大学计算机与通信工程学院	25	95	6.0	8.0