-
题名针对经典排序问题的一种新算法的近似比分析
被引量:1
- 1
-
-
作者
高吉吉
岳雪蓉
陈智斌
-
机构
昆明理工大学理学院
-
出处
《计算机科学》
CSCD
北大核心
2021年第4期37-42,共6页
-
基金
国家自然科学基金(11761042,11461081)。
-
文摘
给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2 ^(q)(q∈Z^(+))的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。
-
关键词
经典排序
近似算法
多项式时间算法
紧例子
一维装箱问题
-
Keywords
Classic scheduling
Approximation algorithm
Polynomial time algorithm
Tight example
One dimensional packing problem
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-