Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421462 | Discrete Applied Mathematics | 2006 | 7 Pages |
Abstract
Let PP be a combinatorial optimization problem, and let AA be an approximation algorithm for PP. The domination ratio domr(A,s)domr(A,s) is the maximal real qq such that the solution x(I)x(I) obtained by AA for any instance II of PP of size ss is not worse than at least the fraction qq of the feasible solutions of II. We say that PP admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm AA for PP 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory Gutin, Tommy Jensen, Anders Yeo,