On the approximability of average completion time scheduling under precedence constraints

Gerhard J. Woeginger

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

7 Citations (Scopus)

Abstract

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 12 (1+5 – √ )≈1.61803.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings
EditorsFernando Orejas, Paul G. Spivakis, Jan van Leeuwen
PublisherSpringer
Pages887-897
ISBN (Electronic)978-3-540-48224-6
ISBN (Print)978-3-540-42287-7
DOIs
Publication statusPublished - 2001
Event28th International Colloquium on Automata, Languages, and Programming, ICALP 2001 - Crete, Greece
Duration: 8 Jul 200112 Jul 2001
Conference number: 28

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2076
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Colloquium on Automata, Languages, and Programming, ICALP 2001
Abbreviated titleICALP
CountryGreece
CityCrete
Period8/07/0112/07/01

Keywords

  • METIS-202688

Fingerprint

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