Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, Ola Svensson · SIAM Journal on Computing · 2019
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 $( icefrac{3}{2}-c)$-approximation algorithm for some fixed $c>0$, improving upon the long-standing bound of $ icefrac{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 $ icefrac{3}{2}$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.