Domination analysis for minimum multiprocessor scheduling

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