Optimization Online


Domination analysis for minimum multiprocessor scheduling

Gregory Gutin (gutin***at***cs.rhul.ac.uk)
Tommy Jensen (tommy***at***cs.rhul.ac.uk)
Anders Yeo (anders***at***cs.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society