Domination analysis for minimum multiprocessor scheduling

Gregory Gutin (gutincs.rhul.ac.uk)
Tommy Jensen (tommycs.rhul.ac.uk)
Anders Yeo (anderscs.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 CSD-TR-03-07; Royal Holloway College, University of London, Egham, Surrey TW20 0EX, UK; July 2003

Download: [Postscript]

Entry Submitted: 07/24/2003
Entry Accepted: 07/24/2003
Entry Last Modified: 07/24/2003

Modify/Update this entry