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

2015/11/24 by Bansal, Nikhil, Srinivasan, Aravind, Svensson, Ola · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1511.07826

Abstract

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 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman & Squillante, SODA, 1999). 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 bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

Cited by

• Improved Online Load Balancing in the Two-Norm

Related

• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
• Improved Approximations for Unrelated Machine Scheduling
• Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
• Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs