Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks |
| |
| Authors: | Jansen and Porkolab |
| |
| Affiliation: | (1) Institut für Informatik und praktische Mathematik, Universit?t zu Kiel, D-24098 Kiel, Germany. kj@informatik.uni-kiel.de., DE;(2) Department of Computing, Imperial College, London SW7 2BZ, England. porkolab@doc.ic.ac.uk., UK |
| |
| Abstract: | Abstract. A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of n independent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed ε > 0 , computes in O(n) time a non-preemptive schedule of length at most (1+ε) times the optimum. |
| |
| Keywords: | . Scheduling Approximation algorithms Linear programming. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
