Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a (3/2-c)-approximation algorithm for some fixed c > 0, improving upon the long-standing bound of 3/2. To do this, we first introduce a new lift-and-project-based SDP relaxation for the problem. This is necessary, as the previous convex programming relaxations have an integrality gap of 3/2. Second, we give a new general bipartiterounding procedure that produces an assignment with certain strong negative correlation properties.