On (1, eps)-Restricted Assignment Makespan Minimization

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 [16] 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 (p_j = 1) or light (p_j = ε), 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.