A Quasi-Polynomial Approximation for the Restricted Assignment Problem

Scheduling jobs on unrelated machines and minimizing the makespan is a classical problem in combinatorial optimization. A job j has a processing time p(ij) for every machine i. The best polynomial algorithm known for this problem goes back to Lenstra et al. and has an approximation ratio of 2. In this paper we study the Restricted Assignment problem, which is the special case where p(ij) is an element of {pj, infinity}. We present an algorithm for this problem with an approximation ratio of 11/6 + epsilon and quasi-polynomial running time n(O(1/epsilon log(n))) for every epsilon > 0. This closes the gap to the best estimation algorithm known for the problem with regard to quasi-polynomial running time.