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 -