Domination analysis for minimum multiprocessor scheduling

Let PP be a combinatorial optimization problem, and let AA be an approximation algorithm for PP. The domination ratio domr(A,s)domr(A,s) is the maximal real qq such that the solution x(I)x(I) obtained by AA for any instance II of PP of size ss is not worse than at least the fraction qq of the feasible solutions of II. We say that PP admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm AA for PP such that lims→∞domr(A,s)=1. 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.