Semidefinite Relaxations for Parallel Machine Scheduling

in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS'98), pp. 472-481.

approximation algorithm, randomized algorithm, convex quadratic program, semidefinite programming, scheduling

What have the problems MaxCut, MaxDiCut, Max2Sat, MaxkCut, and MaxBisection in common? -- "Max", and the fact that the respectively best known approximation algorithm is based on a semidefinite programming relaxation! We extend the random hyperplane technique introduced by Goemans and Williamson for the MaxCut problem and present the first approximation algorithm with constant performance guarantee for a minimization problem based on this approach.

More specifically, we consider the problem of scheduling unrelated parallel machines so as to minimize the total weighted completion time of jobs. Whereas the best previously known approximation algorithms for this problem are based on LP relaxations we give a 3/2-approximation algorithm that relies on a convex quadratic programming relaxation. For the special case of two machines we get a further improvement to a 1.2752-approximation by applying the rounding technique of Goemans and Williamson and its refined version of Feige and Goemans to the solution of a more sophisticated semidefinite programming relaxation. This is the first time that convex and semidefinite programming techniques (apart from LPs) are used in the area of scheduling.

Download as [PDF] [ps.gz]