Approximate sequencing for variable length tasks

CSpace

	Approximate sequencing for variable length tasks
	Cai, MC ; Deng, XT ; Wang, LS
	2003-01-03
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	290 期号:3 页码:2037-2044
摘要	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.
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000179441900039
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/18747
专题	中国科学院数学与系统科学研究院
通讯作者	Cai, MC
作者单位	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
推荐引用方式 GB/T 7714	Cai, MC,Deng, XT,Wang, LS. Approximate sequencing for variable length tasks[J]. THEORETICAL COMPUTER SCIENCE,2003,290(3):2037-2044.
APA	Cai, MC,Deng, XT,&Wang, LS.(2003).Approximate sequencing for variable length tasks.THEORETICAL COMPUTER SCIENCE,290(3),2037-2044.
MLA	Cai, MC,et al."Approximate sequencing for variable length tasks".THEORETICAL COMPUTER SCIENCE 290.3(2003):2037-2044.