Improved Approximations for Unrelated Machine Scheduling

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 L k -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].