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

arXiv: https://arxiv.org/abs/1511.07826 · HTML: https://mlsanity.com/paper/1511.07826/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2015.

## Built on by (most cited first, 2 of 2)

- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)

## Abstract (arXiv)

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.