A combinatorial approximation algorithm for graph balancing with light hyper edges

Makespan minimization in restricted assignment (R|pij ϵ {pj, ∞}|Cmax) is a classical problem in the field of machine scheduling. In a landmark paper in 1990 [9], Lenstra, Shmoys, and Tardos gave a 2-approximation algorithm and proved that the problem cannot be approximated within 1.5 unless P=NP. The upper and lower bounds of the problem have been essentially unimproved in the intervening 25 years, despite several remarkable successful attempts in some special cases of the problem [2, 3, 13] recently. In this paper, we consider a special case called graph-balancing with light hyper edges, where heavy jobs can be assigned to at most two machines while light jobs can be assigned to any number of machines. For this case, we present algorithms with approximation ratios strictly better than 2. Specifically, • Two job sizes: Suppose that light jobs have weight w and heavy jobs have weight W, and