Approximate sequencing for variable length tasks

被引:2
作者
Cai, MC
Deng, XT
Wang, LS
机构
[1] Univ Hong Kong, Inst Syst Sci, Acad Sinica, Kowloon, Hong Kong, Peoples R China
[2] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
关键词
D O I
10.1016/S0304-3975(02)00091-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Based on applications to efficient information gathering over the Web, Czumaj et al. (Algorithms and data structures (Vancouver, BC, 1999), Lecture Notes in Computer Science, Vol. 1663, Springer, Berlin, 1999, p. 297) studied the Variable Length Sequencing Problem (VLSP), showed it is NP-complete, presented a polynomial time algorithm for a very restricted version and an approximation algorithm for a slightly less restricted version. In this paper, we pin-point the difficulty by showing that it is NP-complete in a strong sense even to approximating the VLSP within a factor n(k) for any fixed integer k. In addition, we show it is NP-hard to find the optimal solution even when all jobs follow the periodic property. Motivated by the NP-hardness of approximating VLSP, we consider an optimal version of maximizing the number of completed tasks and present an approximation algorithm with factor 2 and a polynomial time algorithm for optimal solution in the special case when the number of different types of tasks is restricted. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:2037 / 2044
页数:8
相关论文
共 7 条
[1]   Exploring unknown environments [J].
Albers, S ;
Henzinger, MR .
SIAM JOURNAL ON COMPUTING, 2000, 29 (04) :1164-1188
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]  
Bellman R., 1957, DYNAMIC PROGRAMMING
[4]  
Czumaj A, 1999, LECT NOTES COMPUT SC, V1663, P294
[5]  
Deng XT, 1999, J GRAPH THEOR, V32, P265, DOI 10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO
[6]  
2-8
[7]  
1999, WORLD WIDE WEB, V2, P85