Loading...
research article
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.
Type
research article
ArXiv ID
1511.07826
Authors
Publication date
2021
Published in
Volume
50
Issue
3
Start page
STOC16-138
End page
STOC16-159
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
May 10, 2017
Use this identifier to reference this record