  


Domination analysis for minimum multiprocessor scheduling
Gregory Gutin (gutincs.rhul.ac.uk) Abstract: 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. Keywords: combinatorial optimization, domination analysis, minimum multiprocessor scheduling Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Technical Report Number CSDTR0307; Royal Holloway College, University of London, Egham, Surrey TW20 0EX, UK; July 2003 Download: [Postscript] Entry Submitted: 07/24/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  