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.
