2026-08-07T20:31:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18846 2024-03-06T11:02:43Z ddc:004 open_access

On Minimizing Generalized Makespan on Unrelated Machines Ayyadevara, Nikhil Bansal, Nikhil Prabhu, Milind Hardness of Approximation Generalized Makespan 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 [Deng et al., 2023] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Ayyadevara and Nikhil Bansal and Milind Prabhu 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.21 urn:nbn:de:0030-drops-188462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.21 eng https://creativecommons.org/licenses/by/4.0/legalcode