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.
|Title of host publication||Algorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)|
|Editors||D. Halperin, K. Mehlhorn|
|Place of Publication||Berlin|
|Publication status||Published - 2008|
|Name||Lecture Notes in Computer Science|