On Minimizing Generalized Makespan on Unrelated Machines
share
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.
READ FULL TEXT