2023/07/26 by Nikhil Ayyadevara, Nikhil Bansal, Ayyadevara, Nikhil +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2307.13937
openalex publication_date 2023/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 pij 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 Ω(log1/2 n) integrality gap for the natural configuration LP.