一类分批排序问题的复杂性分析及近似算法

• 作者: 张保威 张建伟 郭云飞
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 分批排序 复杂度 近似算法 NP完备性 性能分析
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 数据库与信息处理
• 页码范围: 175-178
• 页数: 4页
• 分类号: TP301
• 字数: 4449字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.03.054

摘要

探讨了分批排序问题,分析了极小化加权总完工时间问题1|B,rj∈{0,r}|∑ωjCj的复杂性,证明了此问题的NP-完备性,并对一类特定问题进行了研究,给出了解决问题的近似算法,证明了其可行性,进而对算法的性能进行了分析,结果表明算法有效地降低了计算复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张建伟	信息工程大学国家数字交换系统工程技术研究中心	62	473	9.0	20.0
3	张保威	郑州轻工业学院计算机与通信工程学院	12	47	4.0	6.0
4	郭云飞	信息工程大学国家数字交换系统工程技术研究中心	23	38	4.0	4.0