Let $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 $\lim_{s\tendsto \infty} \domr(A,s)=1.$ Recently, Alon, Gutin and Krivelevich proved that the partition problem admits an ADRO algorithm. We extend their result to the minimum multiprocessor scheduling problem.
Citation
Technical Report Number CSD-TR-03-07; Royal Holloway College, University of London, Egham, Surrey TW20 0EX, UK; July 2003
Article
View Domination analysis for minimum multiprocessor scheduling