Domination analysis for minimum multiprocessor scheduling

Let image be a combinatorial optimization problem, and let image be an approximation algorithm for image. The domination ratio image is the maximal real image such that the solution image obtained by image for any instance image of image of size image is not worse than at least the fraction image of the feasible solutions of image. We say that image admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm image for image such that image. Alon, Gutin and Krivelevich [Algorithms with large domination ratio, J. Algorithms 50 (2004) 118–131] proved that the partition problem admits an ADRO algorithm. We extend their result to the minimum multiprocessor scheduling problem.