摘要
把由Czumaj等人提出的用于网络信息搜索的任务长度可变的排列问题推广到任务长度可变的多机排序问题,证明该问题的判定形式是NP困难的,而且对任务最大完成数目的优化形式给出了一个近似比α小于4的近似算法.
The Variable Length Multiprocessor Scheduling Problem (VLMSP) is studied. It is based on the Variable Length Sequencing Problem (VLSP), which is proposed by Czumaj et al. and motivated by efficient information gathering over the web. The decision version of VLMSP is proved to be NP-hard and an approximation algorithm with factor α<4 for an optimization version of maximizing the number of completed tasks is presented.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2005年第2期27-30,共4页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目 (10 2 710 65 )
关键词
排列
排序
网络搜索
近似算法
sequencing
scheduling
web searching
approximation algorithm
