@inproceedings{be13111b31f341579151983528d378b1,

title = "Approximability of average completion time scheduling on unrelated machines",

abstract = "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.",

author = "R.A. Sitters",

year = "2008",

doi = "10.1007/978-3-540-87744-8_64",

language = "English",

isbn = "978-3-540-87743-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "768--779",

editor = "D. Halperin and K. Mehlhorn",

booktitle = "Algorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)",

address = "Germany",

}