Variable length sequencing with two lengths

Piotr Berman, Junichiro Fukuyama

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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).

    Original languageEnglish (US)
    Title of host publicationApproximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings
    EditorsKlaus Jansen, Samir Khuller
    PublisherSpringer Verlag
    Number of pages9
    ISBN (Electronic)9783540679967
    StatePublished - 2000
    Event3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000 - Saarbrucken, Germany
    Duration: Sep 5 2000Sep 8 2000

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Variable length sequencing with two lengths'. Together they form a unique fingerprint.

    Cite this