On Minimizing Generalized Makespan on Unrelated Machines

Abstract

We consider the Generalized Makespan Problem (GMP) on unrelated machines, where we are given $n$ jobs and $m$ machines and each job $j$ has arbitrary processing time $p_{ij}$ on machine $i$. Additionally, there is a general symmetric monotone norm ${\psi }_i$ for each machine $i$, that determines the load on machine $i$ as a function of the sizes of jobs assigned to it. The goal is to assign the jobs to minimize the maximum machine load. Recently, Deng, Li, and Rabani (SODA'22) gave a $3$ approximation for GMP when the ${\psi }_i$ are top-$k$ norms, and they ask the question whether an $O(1)$ approximation exists for general norms $\psi$? We answer this negatively and show that, under natural complexity assumptions, there is some fixed constant $\delta >0$, such that GMP is $\Omega ({\log }^{\delta }n)$ hard to approximate. We also give an $\Omega ({\log }^{1/2}n)$ integrality gap for the natural configuration LP.

14 pages