TY - GEN
T1 - Variable length sequencing with two lengths
AU - Berman, Piotr
AU - Fukuyama, Junichiro
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Certain tasks, like accessing pages on the World Wide Web, require duration that varies over time. This poses the following Variable Length Sequencing Problem, or VLSP-L. Let [i, j) denote {i, i+1,…, j− 1}.T he problem is given by a set of jobs J and the time-dependent length function λ: J ×[0, n) → L. A sequencing function σ:J →[0, n) assigns to each job j a time intervalτσ(j) when this job is executed; if σ(j) = t thenτσ(j) = [t, t+λ(j, t)).T he sequencing is valid if these time intervals are disjoint. Our objective is to minimize the makespan, i. e. the maximum ending of an assign time interval. Recently it was shown VLSP-[0, n) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, k} an 2 − 1/k approximation was shown. This paper shows that for k ≥ 3 VLSP-{1, k} is MAX-SNP hard, and that we can approximate it with ratio 2 − 4/(k + 3).
AB - Certain tasks, like accessing pages on the World Wide Web, require duration that varies over time. This poses the following Variable Length Sequencing Problem, or VLSP-L. Let [i, j) denote {i, i+1,…, j− 1}.T he problem is given by a set of jobs J and the time-dependent length function λ: J ×[0, n) → L. A sequencing function σ:J →[0, n) assigns to each job j a time intervalτσ(j) when this job is executed; if σ(j) = t thenτσ(j) = [t, t+λ(j, t)).T he sequencing is valid if these time intervals are disjoint. Our objective is to minimize the makespan, i. e. the maximum ending of an assign time interval. Recently it was shown VLSP-[0, n) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, k} an 2 − 1/k approximation was shown. This paper shows that for k ≥ 3 VLSP-{1, k} is MAX-SNP hard, and that we can approximate it with ratio 2 − 4/(k + 3).
UR - http://www.scopus.com/inward/record.url?scp=84937412498&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937412498&partnerID=8YFLogxK
U2 - 10.1007/3-540-44436-x_7
DO - 10.1007/3-540-44436-x_7
M3 - Conference contribution
AN - SCOPUS:84937412498
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 51
EP - 59
BT - Approximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings
A2 - Jansen, Klaus
A2 - Khuller, Samir
PB - Springer Verlag
T2 - 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000
Y2 - 5 September 2000 through 8 September 2000
ER -