Domination analysis for minimum multiprocessor scheduling |
| |
Authors: | Gregory Gutin Tommy Jensen |
| |
Institution: | a Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK b Department of Computer Science, University of Haifa, Israel c Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstr. 65-67, A-9020 Klagenfurt, Austria |
| |
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 . 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. |
| |
Keywords: | Combinatorial optimization Domination analysis Minimum multiprocessor scheduling |
本文献已被 ScienceDirect 等数据库收录! |
|