# Improved Approximations for Unrelated Machine Scheduling

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

## Key facts

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

## 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 revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted completion time we give a 1.45-approximation, which improves upon the previous 1.488-approximation [Im and Shadloo SODA 2020]. The key technical ingredient in this improvement lies in a new rounding scheme that gives strong negative correlation with less restrictions. For minimizing Lk-norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a √ 4/3-approximation for the L2-norm which improves upon the former √ 2-approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].