针对经典排序问题的一种新算法的近似比分析

• 作者: 高吉吉 岳雪蓉 陈智斌
• 来源期刊: 计算机科学
• 关键词: 经典排序 近似算法 多项式时间算法 紧例子 一维装箱问题
• 年，卷（期）: 2021,（4）
• 所属期刊栏目: 计算机科学理论|Computer Science Theory
• 页码范围: 37-42
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.11896/jsjkx.200600064

摘要

给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题.如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案.Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配.该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法.文章在此基础上,考虑该新算法在一般问题上的近似比.文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2q(q∈Z+)的近似比.紧例子表明,文中对算法的两个版本的分析都是最优的.