机器带准备时间的三台平行机排序问题的线性时间算法

• 作者: 杨启帆 范静
• 来源期刊: 浙江大学学报(理学版)
• 学科: 数学
• 关键词: 排序 近似比 机器准备时间 线性时间
• 年，卷（期）: 2005,（3）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 258-263
• 页数: 6页
• 分类号: O223
• 字数: 7492字
• 语种: 中文
• DOI: 10.3321/j.issn:1008-9497.2005.03.006

摘要

对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数),并证明了当ε=1/5时,对偶阈值算法DA3(1/5)的近似比为6/5,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨启帆	浙江大学数学系	15	209	6.0	14.0
2	范静	浙江大学数学系	1	17	1.0	1.0