2014/10/27 by Deeparnab Chakrabarty, Sanjeev Khanna, Chakrabarty, Deeparnab +3
Arts and Humanities · Computer Science · Health Professions · #Aging, Elder Care, and Social Issues #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Health, Medicine and Society #Hermeneutics and Narrative Identity #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1410.7506
openalex publication_date 2014/10/28 · openalex created_date 2017/03/03 · openalex updated_date 2026/07/28
Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time (2-δ)-approximation algorithm is known for the problem for constant δ> 0. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on any machine but can be assigned to one from a specified subset. Recently in a breakthrough result, Svensson [Svensson, 2011] proved that the integrality gap of a certain configuration LP relaxation is upper bounded by 1.95 for the restricted assignment problem; however, the rounding algorithm is not known to run in polynomial time. In this paper we consider the (1,ε)-restricted assignment problem where each job is either heavy (pj = 1) or light (pj = ε), for some parameter ε > 0. Our main result is a (2-δ)-approximate polynomial time algorithm for the (1,ε)-restricted assignment problem for a fixed constant δ> 0. Even for this special case, the best polynomial-time approximation factor known so far is 2. We obtain this result by rounding the configuration LP relaxation for this problem. A simple reduction from vertex cover shows that this special case remains NP-hard to approximate to within a factor better than 7/6.