任务长度可变的多机排序问题

• 作者: 张少强 陈勇
• 来源期刊: 山东大学学报（理学版）
• 学科: 工学
• 关键词: 排列 排序 网络搜索 近似算法
• 年，卷（期）: 2005,（2）
• 页码范围: 27-30
• 页数: 4页
• 分类号: O224|TP301
• 字数: 3406字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-9352.2005.02.006

摘要

把由Czumaj等人提出的用于网络信息搜索的任务长度可变的排列问题推广到任务长度可变的多机排序问题,证明该问题的判定形式是NP困难的,而且对任务最大完成数目的优化形式给出了一个近似比α小于4的近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈勇	山东大学数学与系统科学学院	9	33	3.0	5.0
5	张少强	天津师范大学数学学院	13	15	3.0	3.0