Approximability of average completion time scheduling on unrelated machines

R.A. Sitters

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

5 Citations (Scopus)
1 Downloads (Pure)


We show that minimizing the sum of completion times on unrelated machines is APX-hard if preemption of jobs is allowed. Additionally, we show that randomized rounding of a convex quadratic program gives a non-preemptive schedule for which the sum of weighted completion times is less than 1.81 times the optimal preemptive sum. This factor is 2.78 if release dates are involved. We sketch how the ratios can be reduced further.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)
EditorsD. Halperin, K. Mehlhorn
Place of PublicationBerlin
ISBN (Print)978-3-540-87743-1
Publication statusPublished - 2008

Publication series

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


Dive into the research topics of 'Approximability of average completion time scheduling on unrelated machines'. Together they form a unique fingerprint.

Cite this