On Minimizing Generalized Makespan on Unrelated Machines

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 $ψ_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 $ψ_i$ are top-$k$ norms, and they ask the question whether an $O(1)$ approximation exists for general norms $ψ$? We answer this negatively and show that, under natural complexity assumptions, there is some fixed constant $δ>0$, such that GMP is $Ω(\log^δ n)$ hard to approximate. We also give an $Ω(\log^{1/2} n)$ integrality gap for the natural configuration LP.