On the approximability of average completion time scheduling under precedence constraints

G.J. Woeginger

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    9 Citations (Scopus)


    We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 1 2 (1+5 v )˜1.61803 .
    Original languageEnglish
    Title of host publicationAutomata, languages and programming : proceedings 28th international colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001
    EditorsF. Orejas, P.G. Spirakis, J. Leeuwen, van
    Place of PublicationBerlin
    ISBN (Print)3-540-48224-5
    Publication statusPublished - 2001

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'On the approximability of average completion time scheduling under precedence constraints'. Together they form a unique fingerprint.

    Cite this